期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that the asymmetric k -center problem is ( log n ) -hard to approximate unless NP DTIME ( n pol y ( log log n ) ) . Since an O ( log n ) -approximation algorithm is known for this problem, this essentially resolves the approximability of this problem. This is the first natural problem whose approximability threshold does not polynomially relate to the known approximation classes. Our techniques also resolve the approximability threshold of the weighted metric k -center problem. We show that it is hard to approximate to within a factor of 3 − for any 0"> 0 .
( log 
