The DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
Open accessAbstract
We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed c > 1 and given any n nodes in ℛ 2 , a randomized version of the scheme finds a (1 + 1/ c )-approximation to the optimum traveling salesman tour in O(n (log n ) O(c) ) time. When the nodes are in ℛ d , the running time increases to O(n (log n ) (O(√ c)) d-1 ). For every fixed c, d the running time is n · poly(log n ), that is nearly linear in n . The algorithmm can be derandomized, but this increases the running time by a factor O(n d ). The previous best approximation algorithm for the problem (due to Christofides) achieves a 3/2-aproximation in polynomial time. We also give similar approximation schemes for some other NP-hard Euclidean problems: Minimum Steiner Tree, k -TSP, and k -MST. (The running times of the algorithm for k -TSP and k -MST involve an additional multiplicative factor k .) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. We also give efficient approximation schemes for Euclidean Min-Cost Matching, a problem that can be solved exactly in polynomial time. All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as ℓ p for p ≥ 1 or other Minkowski norms). They also have simple parallel (i.e., NC) implementations.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
An Effective Heuristic Algorithm for the Traveling-Salesman Problem
Lin, S., & Kernighan, B. W. (1973) · Operations Research · doi:10.1287/opre.21.2.498 · Cited by 3,821
Approximation Algorithms for NP-Hard Problems
(1997) · ACM SIGACT News · doi:10.1145/261342.571216 · Cited by 3,103
Complexity of Computer Computations
(1972) · Springer eBooks · doi:10.1007/978-1-4684-2001-2 · Cited by 2,781
TSPLIB—A Traveling Salesman Problem Library
Reinelt, G. (1991) · ORSA Journal on Computing · doi:10.1287/ijoc.3.4.376 · Cited by 2,616
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
Reducibility Among Combinatorial Problems
Karp, R. M. (2010) · 50 Years of Integer Programming 1958-2008 · doi:10.1007/978-3-540-68279-0_8 · Cited by 2,490
Approximation algorithms for combinatorial problems
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80044-9 · Cited by 2,197
Computer Solutions of the Traveling Salesman Problem
Lin, S. (1965) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1965.tb04146.x · Cited by 1,986
P-Complete Approximation Problems
Sahni, S., & Gonzalez, T. (1976) · Journal of the ACM · doi:10.1145/321958.321975 · Cited by 1,703
Cited by
The Design of Approximation Algorithms
Williamson, D. P., & Shmoys, D. B. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511921735 · Cited by 1,301
Towards a Reliable and Context-Based System Architecture for Autonomous Vehicles
Kain, T., Mundhenk, P., Müller, J.-S., Tompits, H., Wesche, M., & Decke, H. (2020) · OASIcs : OpenAccess Series in Informatics · doi:10.4230/oasics.asd.2020.1 · Cited by 797
Efficient algorithms for online decision problems
Kalai, A., & Vempala, S. (2005) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2004.10.016 · Cited by 591
Discrete cuckoo search algorithm for the travelling salesman problem
Ouaarab, A., Ahiod, B., & Yang, X.-S. (2014) · Neural Computing and Applications · doi:10.1007/s00521-013-1402-2 · Cited by 454
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Tighter Bounds for Graph Steiner Tree Approximation
Robins, G., & Zelikovsky, A. (2005) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480101393155 · Cited by 327
The status of the P versus NP problem
Fortnow, L. (2009) · Communications of the ACM · doi:10.1145/1562164.1562186 · Cited by 321
Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches
Matai, R., Singh, S., & Lal, M. (2010) · Traveling Salesman Problem, Theory and Applications · doi:10.5772/12909 · Cited by 299
An improved LP-based approximation for steiner tree
Byrka, J., Grandoni, F., Rothvoß, T., & Sanità, L. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806769 · Cited by 296
Parameterized Complexity and Approximation Algorithms
Marx, D. (2007) · The Computer Journal · doi:10.1093/comjnl/bxm048 · Cited by 283
Steiner Tree Approximation via Iterative Randomized Rounding
Byrka, J., Grandoni, F., Rothvoss, T., & Sanità, L. (2013) · Journal of the ACM · doi:10.1145/2432622.2432628 · Cited by 281
Pierce, N. A., & Winfree, E. (2002) · Protein Engineering, Design and Selection · doi:10.1093/protein/15.10.779 · Cited by 267
Challenges and opportunities in quantum optimization
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., et al. (2024) · Nature Reviews Physics · doi:10.1038/s42254-024-00770-9 · Cited by 201
“If the problem is restricted to the Euclidean TSP (in which all points are in the d -dimensional space d R and edge weights equal their Euclidean distances), then, remarkably, there exists an explicit PTAS to solve such TSP instances 31 .”
Metadata
- Authors
- Arora, S.
- Venue
- Journal of the ACM
- Published
- 1998-09
- Volume
- 45
- Issue
- 5
- Pages
- 753-782
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2165142526
- Cited by
- 1,137
- References
- 39
- FWCI
- 20.09
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.