p-Center Problems - Location Science - page 84

to avoid sticking at local optima. The computational experiments conducted on
the 40 p-median instances of the OR-Library revealed that the utilization of these
bounds decreases the solution times of Daskin's algorithm.
Other than the meta-heuristic algorithms, Martinich ( 1988 ) proposed a vertex
closing approach for the vertex-restricted p-center problem on complete networks
with distance values that satisfy the triangle inequality. Initially, the algorithm places
a facility on each node and considers the problem of finding n p facilities to
close so that the maximum of the distances between the nodes and their facilities
is minimized. In this study, the optimal solutions were characterized with the
embedded sub-graphs of the original graph. From this analysis, initial lower and
upper bounds were obtained, two polynomial time algorithms were proposed and
procedures to verify the optimality of the solutions for several special cases were
developed. In terms of the number of instances solved to optimality, they outperform
the algorithm by Hochbaum and Shmoys ( 1985 ).
Bozkaya and Tansel ( 1998 ) showed that there exists a spanning tree of any
connected network such that the optimal absolute p-center of this tree is optimal also
for the network under consideration. They conducted experiments on two classes
of spanning trees to observe how often these trees provide the optimal solution.
They concluded that these two classes of spanning trees do not always include the
optimizing tree, but they do in most of the instances.
Mihelic and Robiˇc( 2005 ) solved the vertex-restricted p-center problem by
introducing a heuristic algorithm based on solving a finite series of minimum
dominating set problems. Given a graph G D .V;E/, the minimum dominating
set problem aims to find a node subset S V of minimum cardinality so that any
node in V n S is adjacent to some node in S. They assumed that the underlying
network is complete and the distance values satisfy the triangle inequality. The
computational experiments performed on 40 standard test instances indicate that
their algorithm performs much better than the other polynomial time heuristics
found in the literature and competes with the best known non-polynomial time
algorithms.

4.5 Variants

In this section, we briefly discuss some extensions of the p-center problem.

4.5.1 The Capacitated p -Center Problem

One first variant concerns problems with capacitated facilities. There are few studies
on this variant. Bar-Ilan et al. ( 1993 ) introduced a ten-approximation algorithm for
the special case of unit demands. The guarantee was improved to 6 by Khuller and