文章基本信息

标题：Tight lower bounds for the asymmetric k-center problem
本地全文：下载
作者：Eran Halperin ; Guy Kortsarz ; Robert Krauthgamer 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In the {\sc k -center} problem, the input is a bound k and n points with the distance between every two of them, such that the distances obey the triangle inequality. The goal is to choose a set of k points to serve as centers, so that the maximum distance from the centers C to any point is as small as possible. This fundamental facility location problem is \NP -hard. The symmetric case is well-understood from the viewpoint of approximation; it admits a 2 --approximation, but not better. We address the approximability of the asymmetric k -center problem. Our first result shows that the linear program used by [Archer, 2001] to devise O ( log k ) --approximation has integrality ratio that is at least (1 − o (1)) log n ; this improves on the previous bound 3 of [Archer, 2001]. Using a similar construction, we then prove that the problem cannot be approximated within a ratio of 4 1 log n , unless N P D TIM E ( n log log log n ) . These are the first lower bounds for this problem that are tight, up to constant factors, with the O ( log n ) --approximation due to [Panigrahy and Vishwanathan, 1998] and [Archer, 2001].
关键词：Approximation Algorithms , hardness of approximation , Inapproximability , integrality ratio