Premium
Location problems with grouped structure of demand: Complexity and algorithms
Author(s) -
Averbakh Igor,
Berman Oded
Publication year - 1998
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199803)31:2<81::aid-net3>3.0.co;2-f
Subject(s) - tree (set theory) , set (abstract data type) , time complexity , contrast (vision) , computer science , center (category theory) , mathematics , tree structure , algorithm , polynomial , combinatorics , mathematical optimization , artificial intelligence , mathematical analysis , chemistry , crystallography , programming language , binary tree
We study generalizations of classical multifacility location problems, where customers' demand has a hierarchial structure, i.e., the set of local customers is partitioned into categories (global customers), each having its own requirements for quality of service. For the case of identical facilities, we prove that the categorized coverage, covering, p ‐center, and p ‐median problems are strongly NP‐hard on trees, in contrast with their classical noncategorized versions (which are polynomially solvable on trees). Some of the problems are shown to be NP‐hard even on paths. For the case of distinguishable facilities, we provide polynomial and strongly polynomial algorithms for the categorized covering, multicenter, and multimedian problems with mutual communication on a tree. © 1998 John Wiley & Sons, Inc. Networks 31:81–92, 1998