Generalized p-Center Problems: Complexity Results and Approximation Algorithms


In an earlier paper [Hud91], two "alternative" p-Center problems, where the centers serving customers must be chosen so that exactly one node from each of p prespecified disjoint pairs of nodes is selected, were shown to be NP-complete. This paper considers a generalized version of these problems, in which the nodes from which the p servers are to be selected are partitioned into k sets and the number of servers selected from each set must be within a prespecified range. We refer to these problems as the "Set" p-Center problems. We establish that the triangle inequality (-inequality) versions of these problems, in which the edge weights are assumed to satisfy the triangle inequality, are also NP-complete. We also provide a polynomial time approximation algorithm for the two -inequality "Set" p-Center problems that is optimal for one of the problems in the sense that no algorithm with polynomial running time can provide a better constant factor performance guarantee, unless P=NP.
For the special case "alternative" p-Center problems, which we refer to as the "Pair" p-Center problems, we extend the results in [Hud91] in several ways. For example, the results mentioned above for the "Set" p-Center problems also apply to the "Pair" p-Center problems. Furthermore, we establish and exploit a correspondence between satisfiability and the dominating set type of problems that naturally arise when considering the decision versions of the "Pair" p-Center problems.

Download Information

Click on the following title to view and download the paper in PostScript format.

Generalized p-Center Problems: Complexity Results and Approximation Algorithms (19 pages, 193 KB)
Dorit S. Hochbaum and Anu Pathria. European Journal of Operational Research, 100:3 1997, 594-607.