Location problems with grouped structure of demand: Complexity and algorithms

Journal Article


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

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.