Asymmetric k-center is log* n-hard to approximate

ABSTRACT

In the Asymmetric k-Center problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a set of k points to serve as centers and to assign all the points to the centers, so that the maximum distance of any point to its center is as small as possible. We show that the Asymmetric k-Center problem is hard to approximate up to a factor of log^* n - Θ(1) unless NP ⊆ DTIME(n^{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. We also resolve the approximability threshold of the metric k-Center problem with costs.

REFERENCES

• 1: Sanjeev Arora , Carsten Lund, Hardness of approximations, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 2: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 3: Aaron Archer, Two O (log* k)-Approximation Algorithms for the Asymmetric k-Center Problem, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.1-14, June 13-15, 2001
• 4: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 5: Moses Charikar , Samir Khuller , David M. Mount , Giri Narasimhan, Algorithms for facility location problems with outliers, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.642-651, January 07-09, 2001, Washington, D.C., United States
• 6: M. E. Dyer and A. M. Frieze. A simple heuristic for the p-centre problem. Oper. Res. Lett., 3(6):285--288, 1985.
• 7: I. Dinur, V. Guruswami, and S. Khot. Vertex cover on k-uniform hypergraphs is hard to approximate within factor (k-3-ε). Electronic Colloquium on Computational Complexity (ECCC), (027), 2002.
• 8: Irit Dinur , Venkatesan Guruswami , Subhash Khot , Oded Regev, A new multilayered PCP and the hardness of hypergraph vertex cover, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780629]
• 9: Irit Dinur , Oded Regev , Clifford D. Smyth, The Hardness of 3 - Uniform Hypergraph Coloring, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.33, November 16-19, 2002
• 10: Irit Dinur , Shmuel Safra, The importance of being biased, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509915]
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci., 38(2-3):293--306, 1985.
• 13: Eran Halperin , Robert Krauthgamer, Polylogarithmic inapproximability, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780628]
• 14: Eran Halperin , Guy Kortsarz , Robert Krauthgamer , Aravind Srinivasan , Nan Wang, Integrality ratio for group Steiner trees and directed steiner trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 15: W. L. Hsu and G. L. Nemhauser. Easy and hard bottleneck location problems. Discrete Applied Math., 1(3):209--215, 1979.
• 16: Jonas Holmerin, Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - &egr;, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509986]
• 17: Dorit S. Hochbaum , David B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM (JACM), v.33 n.3, p.533-550, July 1986 [doi>10.1145/5925.5933]
• 18: J. Plesnik. On the computational complexity of centers locating in a graph. Aplikace Matematiky, 25(6):445--452, 1980.
• 19: Rina Panigrahy , Sundar Vishwanathan, An O(log*n) approximation algorithm for the asymmetric p-center problem, Journal of Algorithms, v.27 n.2, p.259-268, May 1, 1998 [doi>10.1006/jagm.1997.0921]
• 20: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 21: D. B. Shmoys. Computing near-optimal solutions to combinatorial optimization problems. In Combinatorial Optimization, pages 355--397. AMS, 1995.
• 22: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, asymmetric k-center, hardness of approximation, metric k-center