×

zbMATH — the first resource for mathematics

Approximation algorithms for the \(k\)-center problem: an experimental evaluation. (English) Zbl 1162.90496
Leopold-Wildburger, Ulrike (ed.) et al., Operations research proceedings 2002. Selected papers of the international conference on operations research (SOR 2002), Klagenfurt, September 2–5, 2002. Berlin: Springer (ISBN 978-3-540-00387-8/pbk). 371-375 (2003).
Summary: We deal with the vertex \(k\)-center problem, a problem which is a part of the discrete location theory. Informally, given a set of cities, with intercity distances specified, one has to pick k cities and build warehouses in them so as to minimize the maximum distance of any city from its closest warehouse. We examine several approximation algorithms that achieve approximation factor of 2 as well as other heuristic algorithms. In particular, we focus on the clustering algorithm by Gonzalez, the parametric pruning algorithm by Hochbaum-Shmoys, and Shmoys’ algorithm. We discuss several variants of the pure greedy approach. We also describe a new heuristic algorithm for solving the dominating set problem to which the k-center problem is often reduced. We have implemented all the algorithms, experimentally evaluated their quality on 40 standard test graphs in the OR-Lib library, and compared their results with the results found in the recent literature.
For the entire collection see [Zbl 1170.90303].

MSC:
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite