Location problems with grouped structure of demand: Complexity and algorithms

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.