2003 | OriginalPaper | Chapter
Approximation Algorithms for the k-center Problem: An Experimental Evaluation
Authors : Jurij Mihelič, Borut Robič
Published in: Operations Research Proceedings 2002
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we deal with the vertex k-center problem, a problewhich 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.