The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Polynomial time approximation schemes for Euclidean TSP and other geometric problems
Abstract
We present a polynomial time approximation scheme for Euclidean TSP in /spl Rfr//sup 2/. Given any n nodes in the plane and /spl epsiv/>0, the scheme finds a (1+/spl epsiv/)-approximation to the optimum traveling salesman tour in time n/sup 0(1//spl epsiv/)/. When the nodes are in /spl Rfr//sup d/, the running time increases to n(O/spl tilde/(log/sup d-2/n)//spl epsiv//sup d-1/) The previous best approximation algorithm for the problem (due to Christofides (1976)) achieves a 3/2-approximation in polynomial time. We also give similar approximation schemes for a host of other Euclidean problems, including Steiner Tree, k-TSP, Minimum degree-k, spanning tree, k-MST, etc. (This list may get longer; our techniques are fairly general.) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as l/sub p/ for p/spl ges/1 or other Minkowski norms).
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
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
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
Bhunia, C. T. (1997) · IETE Journal of Education · doi:10.1080/09747338.1997.11415666 · Cited by 2,701
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
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
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653
Bounds for Certain Multiprocessing Anomalies
Graham, R. L. (1966) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1966.tb01709.x · Cited by 1,647
The Traveling Salesman Problem
(2019) · Fundamentals of Supply Chain Theory · doi:10.1002/9781119584445.ch10 · Cited by 1,614
Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
Ibarra, O. H., & Kim, C. E. (1975) · Journal of the ACM · doi:10.1145/321906.321909 · Cited by 959
Local Search in Combinatorial Optimization
(2018) · Princeton University Press eBooks · doi:10.2307/j.ctv346t9c · Cited by 808
Lau, H. T. (1986) · Lecture Notes in Economics and Mathematical Systems · doi:10.1007/978-3-642-61649-5_4 · Cited by 796
The Euclidean travelling salesman problem is NP-complete
Papadimitriou, C. H. (1977) · Theoretical Computer Science · doi:10.1016/0304-3975(77)90012-3 · Cited by 776
Johnson, D. S., Papadimitriou, C. H., & Yannakakis, M. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90046-3 · Cited by 705
Gilbert, E. N., & Pollak, H. O. (1968) · SIAM Journal on Applied Mathematics · doi:10.1137/0116001 · Cited by 690
An efficient approximation scheme for the one-dimensional bin-packing problem
Karmarkar, N. K., & Karp, R. M. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.61 · Cited by 491
Fast Algorithms for Geometric Traveling Salesman Problems
Bentley, J. J. (1992) · ORSA Journal on Computing · doi:10.1287/ijoc.4.4.387 · Cited by 468
Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
Karp, R. M. (1977) · Mathematics of Operations Research · doi:10.1287/moor.2.3.209 · Cited by 439
Some NP-complete geometric problems
Garey, M. R., Graham, R. L., & Johnson, D. S. (1976) · Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76 · doi:10.1145/800113.803626 · Cited by 400
Approximating clique is almost NP-complete
Feige, U., Goldwasser, S., Lovasz, L., Safra, S., & Szegedy, M. (2002) · [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science · doi:10.1109/sfcs.1991.185341 · Cited by 396
The complexity of facets (and some facets of complexity)
Papadimitriou, C. H., & Yannakakis, M. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90068-0 · Cited by 307
Probabilistic checking of proofs; a new characterization of NP
Arora, S., & Safra, S. (1992) · Proceedings., 33rd Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267824 · Cited by 275
Self-citationApproximation algorithms for geometric problems
Bern, M. W., & Eppstein, D. (1996) · Cited by 118
An approximation scheme for planar graph TSP
Grigni, M., Koutsoupias, E., & Papadimitriou, C. H. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492665 · Cited by 112
The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
Papadimitriou, C. H. (1992) · SIAM Journal on Computing · doi:10.1137/0221030 · Cited by 98
Cited by
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,413
Self-citationWhich Problems Have Strongly Exponential Complexity?
Impagliazzo, R., Paturi, R., & Zane, F. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1774 · Cited by 1,331
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
Arora, S. (1998) · Journal of the ACM · doi:10.1145/290179.290180 · Cited by 1,137
Self-citationEfficient 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
Geometric Shortest Paths and Network Optimization
Mitchell, J. S. B. (2000) · Handbook of Computational Geometry · doi:10.1016/b978-044482537-7/50016-4 · Cited by 427
Metadata
- Authors
- Arora, S.
- Venue
- Proceedings of 37th Conference on Foundations of Computer Science
- Publisher
- IEEE Comput. Soc. Press
- Published
- 2002-12-23
- Pages
- 2-11
- OpenAlex
- W2110367141
- Cited by
- 449
- References
- 28
- FWCI
- 21.68
- Type
- conference paper
- Language
- en
- Open access
- closed
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.