Generalized p-Center problems: Complexity results and approximation algorithms

Dorit S. Hochbaum

doi:10.1016/S0377-2217(96)00076-8

1997-08-01

PRE

Dorit S. Hochbaum

Anu Pathria

DOI：10.1016/S0377-2217(96)00076-8

原文链接

原文求助

摘要

En 中文

In an earlier paper, 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 (Delta-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 Delta-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 previous results 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. (C) 1997 Elsevier Science B.V.

Keyword:

p-Center

approximation algorithms

bottleneck optimization problems

location of facilities