An Analysis of Several Heuristics for the Traveling Salesman Problem
The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
Abstract
Several polynomial time algorithms finding “good,” but not necessarily optimal, tours for the traveling salesman problem are considered. We measure the closeness of a tour by the ratio of the obtained tour length to the minimal tour length. For the nearest neighbor method, we show the ratio is bounded above by a logarithmic function of the number of nodes. We also provide a logarithmic lower bound on the worst case. A class of approximation methods we call insertion methods are studied, and these are also shown to have a logarithmic upper bound. For two specific insertion methods, which we call nearest insertion and cheapest insertion, the ratio is shown to have a constant upper bound of 2, and examples are provided that come arbitrarily close to this upper bound. It is also shown that for any $n\geqq 8$, there are traveling salesman problems with n nodes having tours which cannot be improved by making $n/4$ edge changes, but for which the ratio is $2(1-1/n)$.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“While pioneering approaches for in situ sequencing154,155, transcriptome in vivo analysis156, and multiplex FISH157–159 of single-cell RNA are emerging (see also a recent review160), their throughput and accessibility to the research community have not yet matched those of more established protocols.”
From Revealing the vectors of cellular identity with single-cell genomics (2016) · cites this paper as [154]
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
On the shortest spanning subtree of a graph and the traveling salesman problem
Kruskal, J. B. (1956) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1956-0078686-7 · Cited by 5,088
Shortest Connection Networks And Some Generalizations
Prim, R. C. (1957) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1957.tb01515.x · Cited by 4,565
Floyd, R. W. (1962) · Communications of the ACM · doi:10.1145/367766.368168 · Cited by 3,998
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
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
A Method for Solving Traveling-Salesman Problems
Croes, G. A. (1958) · Operations Research · doi:10.1287/opre.6.6.791 · Cited by 1,570
The Traveling Salesman Problem: A Survey
Bellmore, M., & Nemhauser, G. L. (1968) · Operations Research · doi:10.1287/opre.16.3.538 · Cited by 411
A Heuristic Approach to Solving Travelling Salesman Problems
Karg, R. L., & Thompson, G. L. (1964) · Management Science · doi:10.1287/mnsc.10.2.225 · Cited by 210
Reiter, S., & Sherman, G. (1965) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0113056 · Cited by 112
Research works printed but not linked: 1
- Sartaj Sahni, Teofilo Gonzales, P -complete problems and approximate solutions, 15th Annual Symposium on Switching and Automata Theory (Univ. New Orleans, New Orleans, La., 1974), IEEE Comput. Soc., Long Beach, Calif., 1974, 28–32 MR0416113 (54:4189) · doi:10.1109/swat.1974.22
Cited by
Items 901–1,000 of 1,000
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0006
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0003
The Grand Unified Theory of Computation
Cristopher, M. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0007
Interaction and Pseudorandomness
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0011
Who is the Hardest One of All? NP-Completeness
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0005
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0008
A locally optimal insertion heuristic for a one-machine scheduling problem
Werner, F. M. (1990) · RAIRO - Operations Research · doi:10.1051/ro/1990240302551
Introduction and solutions to NOE path planning with incomplete information
Hua-de, L., & Suraweera, F. (2002) · IEEE Region 10 Conference (TENCON) · doi:10.1109/tencon.1993.320545
Pérez, I. T. (2016) · Institutional Repository of the University of Granada (University of Granada)
Population Iterative Annealing Algorithm with Improved Inver-over Operator for TSP
Yuan, Z., & Zhang, Y. (2016) · International Conference on Modeling, Simulation and Optimization Technologies and Applications (MSOTA) · doi:10.2991/msota-16.2016.59
Zhang, B. (2011) · VTechWorks (Virginia Tech)
On global integer extrema of real-valued box-constrained multivariate quadratic functions
Wörz, S. (2017) · Journal of Combinatorial Optimization · doi:10.1007/s10878-017-0123-3
An algorithm for solving the traveling-salesman problem with three-dimensional polygonal barriers
Lee, Y.-G. (1992) · OhioLink ETD Center (Ohio Library and Information Network)
Request-Allocation in Dynamic Collaborative Transportation Planning Problems
Schopka, K., & Kopfer, H. (2017) · Operations research proceedings · doi:10.1007/978-3-319-55702-1_44
Chapter 13: Bio‒Inspired Computing Paradigms
(2017) · CRC Press eBooks · doi:10.1201/9781315207353-14
Continuous caster scheduling, an optimization approach using column generation
Jawahir, K. (1998) · TSpace (University of Toronto)
Contributions to the solution of the symmetric travelling salesman problem
Krishnamoorthy, M. (1991) · Spiral (Imperial College London)
Es viable una red de autobuses sin líneas
Medina, M. F., Peñas, I. Y. G. D. L., & Ruiz, S. S. (2017) · Library Open Repository (Universidad Complutense Madrid)
Min, H. J., & Lim, H.-S. (2017) · International Journal of Distributed Sensor Networks · doi:10.1177/1550147717741265
Coordination of Cooperative Multi-Robot Teams
Klodt, L. (2017) · Technischen Universität Darmstadt · doi:10.26083/tuprints-00007026
Hierarchical Reinforcement Learning: Approximating Optimal Discounted TSP Using Local PoliciesPreprint
Zahavy, T., Hasidim, A., Kaplan, H. Y., & Mansour, Y. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.04674
A hybrid metaheuristics for layout optimization in production cell
Zupan, H., Žerovnik, J., & Herakovič, N. (2015) · International Conference on Advances in Mechanical and Automation Engineering (MAE) · doi:10.15224/978-1-63248-080-4-76
Incorporating Traffic Management Information into Logistics Planning
Köster, F. (2018) · Digitale Bibliothek Braunschweig (Verbundzentrale Göttingen (VZG)) · doi:10.24355/dbbs.084-201801101209
Distributed Lower Bounds: Lovász Local Lemma, Mobile Agents, Cops and Robbers
Brandt, S. (2018) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-b-000281250
Accommodating Plan Revisions with Multiple Agents for Local Search in Road Networks
Moore, D., Bihl, T., Jenkins, T., & Archibald, C. (2018) · IEEE National Aerospace and Electronics Conference (NAECON) · doi:10.1109/naecon.2018.8556767
Advanced analytics through FPGA based query processing and deep reinforcement learning
Malazgirt, G. A. (2019) · UPCommons institutional repository (Universitat Politècnica de Catalunya) · doi:10.5821/dissertation-2117-129265
Kyritsis, M., Din, S. U., & Gulliver, S. R. (2018) · HCT Information Technology Trends (ITT) · doi:10.1109/ctit.2018.8649545
Ütemezési feladatokra alkalmazott genetikus algoritmus keresztező operátorainak vizsgálata
Simon, P. (2014) · Műszaki Tudományos Közlemények · doi:10.33895/mtk-2014.01.16
Jose, A. F. A., Durai, C. A. D., & Livingston, S. J. (2018) · International Journal of Engineering & Technology · doi:10.14419/ijet.v7i3.14522
Vo, N. T., Le, L. D., Huynh, V. Q., Tran, T. L., & Nguyen, H. D. (2019) · Science and Technology Development Journal - Natural Sciences · doi:10.32508/stdjns.v2i2.730
Minimum-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratioPreprint
Deǐneko, V. G., & Tiskin, A. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0711.2399
Exponential Time Approximation Scheme for TSP
Chen, Z., Feng, Q., Fu, B., Lin, M., & Wang, J. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-27195-4_11
Hackfeld, J. (2019) · DepositOnce · doi:10.14279/depositonce-8714
A Family of Unsupervised Sampling Algorithms
Guillaume, S., & Ros, F. (2019) · Unsupervised and semi-supervised learning · doi:10.1007/978-3-030-29349-9_3
Um problema de otimização de rotas com janelas temporais
Mesquita, M. M. (2019) · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT)
Accelerating DNA Computing via PLP-qPCR Answer Read out to Solve Traveling Salesman Problems
Xiong, F. S., Kuby, M., & Frasch, W. D. (2020) · IntechOpen eBooks · doi:10.5772/intechopen.91663
Hidayat, R. M. (2018) · Universitas Pasundan institutional repositories & scientific journals (Universitas Pasundan)
Exploration of Time-Varying Connected Graphs with Silent Agents
Dobrev, S., Kráľovič, R., & Pardubská, D. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-54921-3_9
Multiple Resource Network Voronoi Diagram
Qutbuddin, A., & Yang, K. (2021) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2021.3088147
Montgomery, C. (2020) · DSpace@MIT (Massachusetts Institute of Technology)
Islam, K. J. (2020) · Nottingham ePrints (University of Nottingham)
Gou, J., Wang, L., Lin, H., & Peng, M. (2020) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-030-64002-6_12
A Blockchain-based computation offloading approach with result verification
Körbel, B. (2020) · reposiTUm (TU Wien) · doi:10.34726/hss.2021.80381
A partitioning column approach for solving LED sorter manipulator path planning problems
Chen, S., & Tseng, Y.-C. (2021) · Journal of Industrial and Management Optimization · doi:10.3934/jimo.2021055
Assistenzsysteme für verteilte Veranstaltungen
Schaller, R. D. (2016) · OPUS Repository (Kooperativer Bibliotheksverbund Berlin-Brandenburg)
Exploiting Digitalization to Determine Optimal Intervention Programs for Water Distribution Networks
Kerwin, S. M. (2020) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-b-000465735
Network Function Virtualization Service Delivery In Future Internet
Zheng, D. (2021) · Digital Archive @ GSU · doi:10.57709/22396797
LOGÍSTICA PARA ROTAS DE DISTRIBUIÇÃO: UM ESTUDO DE CASO
Ribeiro, J. F. F., & Galli, P. R. (2021) · Revista Latino-Americana de Inovação e Engenharia de Produção · doi:10.5380/relainep.v9i15.80153
An Enhanced Analog Nearest Neighbor Algorithm for Route Planning After a Major Disaster
Magnaye, R. B., Sauser, B. J., Sohail S., C., & Rakotobe-Joel, T. (2021) · International Journal of Operations and Quantitative Management · doi:10.46970/2021.26.4.1
Enhanced performance testing and monitoring of JVM-based distributed data-processing applications
Nickel, B. (2015) · reposiTUm (TU Wien) · doi:10.34726/hss.2015.32880
Network Design with Non Simultaneous Flows
Lucertini, M., & Paletta, G. (1984) · Courses and lectures · doi:10.1007/978-3-7091-4338-4_4
Hasta Ergonomisi Açısından Servis Güzergâhlarının İyileştirilmesi
GUNESEN, B., & Kapanoğlu, M. (2021) · Uluslararası mühendislik araştırma ve geliştirme dergisi · doi:10.29137/umagd.1014407
Partitioning Into Prescribed Number of Cycles and Mod k T-join With Slack
Barrett, J. M., Bendayan, S., Li, Y., & Reed, B. A. (2021) · Procedia Computer Science · doi:10.1016/j.procs.2021.11.006
(2005) · Elsevier eBooks · doi:10.1016/b978-155860872-6/50030-5
Paschos, V. T. (2014) · Wiley eBooks · doi:10.1002/9781119005353.biblio
Cook, W. J., Cunningham, W. H., Pulleyblank, W. R., & Schrijver, A. (1997) · Wiley eBooks · doi:10.1002/9781118033142.biblio
(1988) · Wiley eBooks · doi:10.1002/9781118627372.refs
Snyder, L., & Shen, Z. M. (2019) · Wiley eBooks · doi:10.1002/9781119584445.refs
Deroussi, L. (2016) · Wiley eBooks · doi:10.1002/9781119136583.biblio
GRAPH PLAYGROUND: A PEDAGOGIC TOOL FOR GRAPH THEORY AND ALGORITHMS
Adhikari, N. (2021) · Digital Commons - URI (University of Rhode Island) · doi:10.23860/thesis-adhikari-neeraj-2021
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0001
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0015
A Problem-Based Heuristic for Asymmetric Travelling Salesman Problems
Putponpai, J., & Pongchairerks, P. (2014) · Journal of Industrial and Intelligent Information · doi:10.12720/jiii.3.3.258-265
(2018) · Elsevier eBooks · doi:10.1016/b978-0-12-809786-1.16001-1
(2002) · A K Peters/CRC Press eBooks · doi:10.1201/b10621-7
Agrawal, P., Kaur, H., & Bhardwaj, D. (2012) · INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY · doi:10.24297/ijct.v2i2b.6734
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0002
Multistage Production and Distribution Planning Problems
Geunes, J. (2014) · CRC Press eBooks · doi:10.1201/b17414-11
Turau, V. (2004) · Oldenbourg Wissenschaftsverlag eBooks · doi:10.1524/9783486593778.bm
Concurrent counting is harder than queuing
Tirthapura, S., & Busch, C. (2006) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2006.1639327
Instance-Specific Parameter Tuning for Meta-Heuristics
Ries, J., Beullens, P., & Wang, Y. (2015) · IGI Global eBooks · doi:10.4018/978-1-4666-7456-1.ch072
Sequential Optimization Under Uncertainty: Models, Algorithms, and Applications
Yu, X. (2022) · Deep Blue (University of Michigan) · doi:10.7302/4585
Quantum-Inspired Optimization over Permutation GroupsPreprint
Munukur, R., Bardhan, B. R., Upadhyay, D. K., & Ghosh, J. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2212.02669
Mrdja, P., Kitanović, M., Miljic, N., & Popovic, S. (2022) · IOP Conference Series Materials Science and Engineering · doi:10.1088/1757-899x/1271/1/012005
(2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.002.0007
(2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.002.0004
(2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.002.0003
(2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.005.0001
(2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.002.0006
OPTIMIZATION TOOLS TO SUPPORT AUTOMATED MATERIAL HANDLING SYSTEM DESIGN
Brewer, M. A., & Taylor, G. D. (2023) · International Conference on Flexible Automation and Integrated Manufacturing (FAIM) · doi:10.1615/faim1999.470
Multi-Objective Policy Evolution for a Same-Day Delivery Problem with Soft Deadlines
Frohner, N., Raidl, G. R., & Chicano, F. (2023) · Genetic and Evolutionary Computation Conference Companion (GECCO Companion) · doi:10.1145/3583133.3596381
Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics
Klootwijk, S., & Manthey, B. (2023) · Algorithmica · doi:10.1007/s00453-023-01167-3
Enhancing Big Data Conversion Validation with Alpha-Lightweight Coreset
Hoang, N. L., & Dang, T. K. (2023) · SN Computer Science · doi:10.1007/s42979-023-02206-0
Optymalizacja w logistyce, tom 2. Modelowanie przepływów w kanałach dystrybucji
Jadczak, R., Karwacki, Z., & Miszczyński, P. (2020) · Wydawnictwo Uniwersytetu Łódzkiego eBooks · doi:10.18778/8220-165-9
Das stochastisch-dynamische Multi-Vehicle Inventory-Routing-Problem für Bike-Sharing-Systeme
Brinkmann, J. (2023) · Springer eBooks · doi:10.1007/978-3-031-16536-8_5
Perpetual Sensor Networks with the Minimum Number of Mobile Chargers
Le, M. Q., Hung, N. N., Nguyen, K. T., Nguyen, P. L., & Do, P. T. (2023) · International Symposium on Information and Communication Technology · doi:10.1145/3628797.3628970
PROPOSTA DE MÉTODO HEURÍSTICO APLICADO AO PROBLEMA DE MICROAGREGAÇÃO MULTIVARIADO
Fadel, A. C., Ochi, L. S., Brito, J. A. M., & Semaan, G. S. (2018) · Anais do Simpósio Brasileiro de Pesquisa Operacional · doi:10.59254/sbpo-2018-85390
Uma Formulação MILP para Procedimentos de Busca Local com Melhorias k-Opt
Michels, A. S., Sikora, C. G. S., Lopes, T. C., & Magatão, L. (2018) · Anais do Simpósio Brasileiro de Pesquisa Operacional · doi:10.59254/sbpo-2018-85357
Time-Efficient Covert Multicast in Uav-Enabled Wireless Communication SystemsPreprint
Zhang, W., He, J., Shen, Y., & Jiang, X. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4875390
A New Approach to Solve the Classical Symmetric Traveling Salesman Problem by Highest Suffix Method
Mallick, K. K., Sweet, M. F. R., Biswas, T. K., Sikder, R. R., Kabir, M., & Hasan, M. T. (2024) · International Journal of Computer Applications · doi:10.5120/ijca2024923498
Traveling salesman problem with backend information processing
Doganbas, M., & Shin, H. (2024) · Operations Research Letters · doi:10.1016/j.orl.2024.107193
Machina, K., Kim, J.-H., & Ahmed, A. (2024) · Computer Engineering and Intelligent Systems · doi:10.7176/ceis/15-1-10
Hybrid Heterogeneous Wireless Chargers Placement
Hou, S., Peng, D., Ren, M., Xu, Y., Zhu, Y., Dai, H., & Wu, L. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-71467-2_27
Novel Theory and Method in WRSNs
Lin, C., Sun, Y., & Yang, W. J. (2024) · Wireless networks · doi:10.1007/978-981-97-9543-7_7
Scheduling Optimization Methodology
Lin, C., Sun, Y., & Yang, W. (2024) · Wireless networks · doi:10.1007/978-981-97-9543-7_3
Metadata
- Authors
- Rosenkrantz, D. J., Stearns, R. E., & Lewis, II
- Affiliations
- General Electric (United States) (US)
- Venue
- SIAM Journal on Computing
- Published
- 1977-09
- Volume
- 6
- Issue
- 3
- Pages
- 563-581
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2956015669
- Cited by
- 837
- References
- 14
- Citations by year
- 2026: 39 · 2025: 40 · 2024: 46 · 2023: 42 · 2022: 33 · 2021: 45 · 2020: 34 · 2019: 36 · 2018: 32 · 2017: 31 · 2016: 25 · 2015: 25 · 2014: 32 · 2013: 29 · 2012: 23
- FWCI
- 2.91
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Computing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Vehicle Routing Optimization Methods
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computational Geometry and Mesh Generation
- Keywords
- traveling salesman problem, approximation algorithms, polynomial-time heuristic, nearest neighbor algorithm, insertion method, logarithmic approximation ratio, worst-case analysis
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.