Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate. (English) Zbl 1192.68314
Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 21-27, electronic only (2004).
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W25 | Approximation algorithms |
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | S. Arora and C. Lund. Hardness of approximation. In Dorit Hochbaum, editor, Approximation Algorithms for NP Hard Problems. PWS publishing Co, 1996.]] · Zbl 1368.68010 |
| [2] | S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. JACM, 45(3):501-555, 1998.]] 10.1145/278298.278306 · Zbl 1065.68570 |
| [3] | A. F. Archer. Two O(log*k)-approximation algorithms for the asymmetric k-center problem. Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization, pages 1-14, 2001.]] · Zbl 1010.90513 |
| [4] | S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. JACM, 45(1):70-122, 1998.]] 10.1145/273865.273901 · Zbl 0903.68076 |
| [5] | M. Charikar, S. Khuller, D. M. Mount, and G. Narasimhan. Algorithms for facility location problems with outliers. Proceedings of the ACM-SIAM symposium on Discrete Algorithms 2001.]] |
| [6] | M. E. Dyer and A. M. Frieze. A simple heuristic for the p-centre problem. Oper. Res. Lett., 3(6):285-288, 1985.]] · Zbl 0556.90019 |
| [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] | I. Dinur, V. Guruswami, S. Khot, and O. Regev. A new multilayered PCP and the hardness of hypergraph vertex cover. Proceedings of the 35th ACM Symposium on Theory of Computing, 2003.]] 10.1145/780542.780629 · Zbl 1192.68290 |
| [9] | I. Dinur, O. Regev, and C. D. Smyth. The hardness of 3-uniform hypergraph coloring. Proceedings of the 43rd IEEE conference on Foundations of Computer Science, 2002.]] |
| [10] | I. Dinur and S. Safra. The importance of being biased. Proceedings of the 34th ACM Symposium on Theory of Computing, 2002.]] 10.1145/509907.509915 · Zbl 1192.68318 |
| [11] | M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, 1979.]] · Zbl 0411.68039 |
| [12] | T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci., 38(2-3):293-306, 1985.]] · Zbl 0567.62048 |
| [13] | E. Halperin and R. Krauthgamer. Polylogarithmic inapproximability. Proceedings of the 35th ACM Symposium on Theory of Computing, 2003.]] 10.1145/780542.780628 · Zbl 1192.68321 |
| [14] | E. Halperin, G. Kortsarz, R. Krauthgamer, A. Srinivasan, and N. Wang. Integrality ratio for group steiner trees and directed steiner trees. Proceedings of the 14th SIAM Symposium on Discrete Algorithms, 2003.]] · Zbl 1094.68611 |
| [15] | W. L. Hsu and G. L. Nemhauser. Easy and hard bottleneck location problems. Discrete Applied Math., 1(3):209-215, 1979.]] · Zbl 0424.90049 |
| [16] | J. Holmerin. Vertex cover on 4-regular graphs is hard to approximate within 2-ε. Proceedings of the 34th ACM Symposium on Theory of Computing, pages 544-552, 2002.]] 10.1145/509907.509986 |
| [17] | D. S. Hochbaum and D. B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. JACM, 33(3):533-550, 1986.]] 10.1145/5925.5933 |
| [18] | J. Plesnik. On the computational complexity of centers locating in a graph. Aplikace Matematiky, 25(6):445-452, 1980.]] · Zbl 0454.68026 |
| [19] | R. Panigrahy and S. Vishwanathan. An O(log* n) approximation algorithm for the asymmetric p-center problem. J. of Algorithms, 27(2):259-268, 1998.]] 10.1006/jagm.1997.0921 · Zbl 0917.68201 |
| [20] | R. Raz. A parallel repetition theorem. SIAM J. of Computing, 27(3):763-803, 1998.]] 10.1137/S0097539795280895 · Zbl 0911.68082 |
| [21] | D. B. Shmoys. Computing near-optimal solutions to combinatorial optimization problems. In Combinatorial Optimization, pages 355-397. AMS, 1995.]] · Zbl 0835.90081 |
| [22] | V. V. Vazirani. Approximation Algorithms. Springer Verlag, 2001.]] |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
