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 601–700 of 1,000
Royal Lineage Genetic Algorithm for a Better Solution to Traveling Salesman Problem
Firdaus, H., & Widianti, T. (2024) · International Symposium INFOTEH-JAHORINA (INFOTEH) · doi:10.1109/infoteh60418.2024.10496037 · Cited by 4
On Replacing Cryptopuzzles with Useful Computation in Blockchain Proof-of-Work Protocols
Merlina, A., Garrett, T., & Vitenberg, R. M. (2026) · ACM Computing Surveys · doi:10.1145/3828717 · Cited by 4
ACOℝ-V - An algorithm that incorporates the visibility heuristic to the ACO in continuous domain
Conti, C. R., Roisenberg, M., & Neto, G. S. (2012) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2012.6252921 · Cited by 4
Contribution of simple heuristics for the vehicle routing problem - A case study of a small brewery
Kučera, P., & Krejčí, I. (2013) · Acta Universitatis Agriculturae et Silviculturae Mendelianae Brunensis · doi:10.11118/actaun201361072393 · Cited by 4
Dewi, P. S., Triyani, T., & Nurshiami, S. R. (2021) · Jurnal Ilmiah Matematika dan Pendidikan Matematika · doi:10.20884/1.jmp.2020.12.2.3617 · Cited by 4
Jacquelin, M., Ng, E., & Peyton, B. W. (2021) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/20m1368070 · Cited by 4
The Traveling Salesman Problem
Körte, B., & Vygen, J. (2000) · Algorithms and combinatorics · doi:10.1007/978-3-662-21708-5_21 · Cited by 4
An efficient procedure for obtaining feasible solutions to the n-city traveling salesman problem
Feiring, B. R. (1990) · Mathematical and Computer Modelling · doi:10.1016/0895-7177(90)90371-s · Cited by 4
A Semidefinite Relaxation for Air Traffic Flow Scheduling
d’Aspremont, A., & Ghaoui, L. E. (2007) · RIVF International Conference on Computing and Communication Technologies (RIVF) · doi:10.1109/rivf.2007.369142 · Cited by 4
Guimarães, T. A., Scarpin, C. T., & Steiner, M. T. A. (2015) · Gestão & Produção · doi:10.1590/0104-530x1044/13 · Cited by 4
Optimal Scheduling for Interference Mitigation by Range Information
Yajnanarayana, V., Magnusson, K. E. G., Brandt, R., Dwivedi, S., & Händel, P. (2017) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2017.2688417 · Cited by 4
A Sketch-First Approach for Finding TSP
Huang, W., Yu, J. X., & Shang, Z. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-46922-5_10 · Cited by 4
Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems
Bringmann, K., Engels, C., Manthey, B., & Rao, B. V. R. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40313-2_21 · Cited by 4
Determination of minimum three-dimensional cutting-tool paths in the presence of barriers
Williams, R. L., & Lee, Y.-G. (1993) · Computers & Industrial Engineering · doi:10.1016/0360-8352(93)90258-y · Cited by 4
Different versions of the savings method for the time limited vehicle routing problem
Kučera, P. (2013) · Acta Universitatis Agriculturae et Silviculturae Mendelianae Brunensis · doi:10.11118/actaun201260070171 · Cited by 4
Ant Colony Optimization Based on Estimation of Distribution for the Traveling Salesman Problem
Chang, X., Xu, J., & Huiyou, C. (2009) · International Conference on Natural Computation (ICNC) · doi:10.1109/icnc.2009.165 · Cited by 4
A General Heuristic for Node Routing Problems
Lapalme, G., Potvin, J., & Rousseau, J. M. (1988) · Lecture notes in economics and mathematical systems · doi:10.1007/978-3-642-46629-8_9 · Cited by 4
A survey of workforce scheduling and routing
Castillo-Salazar, A., Landa-Silva, D., & Qu, R. (2012) · Cited by 4
Review of Tour Generation for Solving Traveling Salesman Problems
Ouaarab, A. (2020) · Springer tracts in nature-inspired computing · doi:10.1007/978-981-15-1842-3_4 · Cited by 4
The Traveling Salesman Problem
Körte, B., & Vygen, J. (2002) · Algorithms and combinatorics · doi:10.1007/978-3-662-21711-5_21 · Cited by 4
A tabu search methodology for spacecraft tour trajectory optimization
Johnson, G. P. (2014) · Texas ScholarWorks (Texas Digital Library) · Cited by 4
Compression of Boolean inverted files by document ordering
Gelbukh, A. F., Han, S., & Sidorov, G. (2004) · International Conference on Natural Language Processing and Knowledge Engineering (NLPKE) · doi:10.1109/nlpke.2003.1275907 · Cited by 4
Solving Traveling Salesman Problem With a non-complete Graph
Taba, E., & Sadat, M. (2010) · UWSpace (University of Waterloo) · Cited by 4
Density-Based Clustering Heuristics for the Traveling Salesman Problem
Agostinelli, M. (2017) · Digital Commons - URI (University of Rhode Island) · doi:10.23860/thesis-agostinelli-matthew-2017 · Cited by 4
Planning in Hierarchical Reinforcement Learning: Guarantees for Using Local PoliciesPreprint
Zahavy, T., Hasidim, A., Kaplan, H. Y., & Mansour, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.10140 · Cited by 4
On the Approximation Ratio of the $k$-Opt and Lin-Kernighan AlgorithmPreprint
Zhong, X. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.12755 · Cited by 4
Efficient IoT application delivery and management in smart city environments
Vögler, M. (2016) · reposiTUm (TU Wien) · doi:10.34726/hss.2016.36350 · Cited by 4
Exploiting Edited Large Language Models as General Scientific OptimizersPreprint
Lv, Q., Liu, T., & Wang, H. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2503.09620 · Cited by 4
Habib, A. Z. S. B., Ahamed, M. Y., Gyawali, P., Doretto, G., & Adjeroh, D. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2606.05441 · Cited by 4
Influence of multiple spreaders through farthest first traversal
Ramrakhiyani, M., Tiwari, M., & Sunitha, V. (2024) · Applied Network Science · doi:10.1007/s41109-024-00676-6 · Cited by 3
Dinh, Q. T., Dang, T. H., Hà, M. H., Vu, D. M., & Mai, T. (2025) · Journal of the Operational Research Society · doi:10.1080/01605682.2025.2519991 · Cited by 3
POSTCONDBENCH: Benchmarking Correctness and Completeness in Formal Postcondition Inference
Zhang, G., & Zhai, J. (2026) · Findings of the Association for Computational Linguistics: ACL (Findings of ACL) · doi:10.18653/v1/2026.findings-acl.1768 · Cited by 3
Approximation Algorithms for Vehicle Routing Problems: A Survey
Zhao, J., Khalid, U., Paing, S. N., Zhang, C., Zhan, Z., & Shin, H. (2026) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2026.3731146 · Cited by 3
Hyper-heuristics with Path Relinking applied to the Generalised Time-Dependent ATSP in air travel
Simões, M. D. M. D., Bahiense, L., & de Figueiredo, C. M. H. (2023) · Procedia Computer Science · doi:10.1016/j.procs.2023.08.211 · Cited by 3
Phoa, F. K. H., & Wong, K. T. (2024) · Lecture notes in computer science · doi:10.1007/978-981-97-7184-4_1 · Cited by 3
Aloise, D., Moine, R., Ribeiro, C. C., & Jalbert, J. (2025) · European Journal of Operational Research · doi:10.1016/j.ejor.2025.04.019 · Cited by 3
Soimun, A., Puritasari, N. M. M., & Sadri, P. D. A. (2025) · Jurnal Penelitian Sekolah Tinggi Transportasi Darat · doi:10.55511/jpsttd.v16i1.722 · Cited by 3
Courier Working Time Aware Vehicle Scheduling for Efficient Urban Logistics
Lyu, W., Wang, H., Song, Y., Wang, S., Liu, Y., He, T., & Zhang, D. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3613677 · Cited by 3
On the Nearest-Neighbor Algorithm for the Mean-Field Traveling Salesman Problem
Bandyopadhyay, A., & Sajadi, F. A. (2014) · Journal of Applied Probability · doi:10.1017/s0001867800010119 · Cited by 3
An Ant Colony System-based Optimization Scheme of Data Mining
Xingliang, Z., & Li, J. (2006) · International Conference on Intelligent Systems Design and Applications (ISDA) · doi:10.1109/isda.2006.89 · Cited by 3
Algorithms And Procedures Of Determining The Optimal Route In The Graph
Sokas, A. (2013) · International Conference Transbaltica · doi:10.3846/transbaltica2013.045 · Cited by 3
Augmented tour construction heuristics for the travelling salesman problem
Ursani, Z., & Ursani, A. A. (2023) · International Journal of Industrial Optimization · doi:10.12928/ijio.v4i2.7875 · Cited by 3
HiTSP: Towards a Hierarchical Neural Framework for Large-scale Traveling Salesman Problems
Liu, J.-F., Wang, Z., Zhang, W., Zhang, C., Hou, J., Bai, B. B., & Zhang, G. (2023) · Journal of the Operations Research Society of China · doi:10.1007/s40305-023-00507-y · Cited by 3
Kim, W., Jeong, J., Kim, T. H., & Lee, K. (2025) · Entropy · doi:10.3390/e27030251 · Cited by 3
Optimization of automatized picking process
Agárdi, A., Kovács, L., & Bányai, T. (2019) · IEEE International Symposium on Applied Computational Intelligence and Informatics (SACI) · doi:10.1109/saci46893.2019.9111597 · Cited by 3
A Hybrid BSO-ACS Algorithm for Vehicle Routing Problem with Time Windows on Road Networks
Liu, M., Shen, Y., Zhao, Q. G., & Shi, Y. (2020) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec48606.2020.9185868 · Cited by 3
Novel Trends in the Traveling Salesman Problem
Davendra, D. D., & Bialic-Davendra, M. (2019) · IntechOpen eBooks · doi:10.5772/intechopen.78197 · Cited by 3
Potvin, J., Lapalme, G., & Rousseau, J. M. (1992) · doi:10.1007/978-1-349-12362-9_20 · Cited by 3
Solving Quadratic Traveling Salesman Problem with Deep Reinforcement Learning
Zhang, H., Zhang, Z., Chen, J., & Wang, J. (2022) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/smc53654.2022.9945424 · Cited by 3
Bittencourt, G. P., Marques, J. P. P. G., & Cunha, D. C. (2023) · Computer Communications · doi:10.1016/j.comcom.2023.08.021 · Cited by 3
UAV-Assisted Data Collection and Transmission Using Petal Algorithm in Wireless Sensor Networks
Li, X., Tao, M., & Yang, S. (2024) · Lecture notes in computer science · doi:10.1007/978-981-97-0862-8_8 · Cited by 3
The cost efficiency of sampling designs
Liberts, M. (2013) · Statistics in Transition New Series · doi:10.59170/stattrans-2013-001 · Cited by 3
Online Network Design with Outliers
Anagnostopoulos, A., Grandoni, F., Leonardi, S., & Sankowski, P. (2015) · Algorithmica · doi:10.1007/s00453-015-0021-y · Cited by 3
Park, B., Choi, Y., & Park, H. (2014) · Tunnel and Underground Space · doi:10.7474/tus.2014.24.1.011 · Cited by 3
Concurrent counting is harder than queuing
Busch, C., & Tirthapura, S. (2010) · Theoretical Computer Science · doi:10.1016/j.tcs.2010.07.002 · Cited by 3
Real-time multicast routing with optimal network cost
Jia, X., Cao, J., & Jia, W. (2002) · IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA) · doi:10.1109/rtcsa.1996.554960 · Cited by 3
Su, C., & Chen, H. (1999) · Journal of the Chinese Institute of Industrial Engineers · doi:10.1080/10170669.1999.10432667 · Cited by 3
Weighted Nearest Neighbor Algorithms for the Graph Exploration Problem on Cycles
Asahiro, Y., Miyano, E., Miyazaki, S., & Yoshimuta, T. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-69507-3_13 · Cited by 3
The travelling salesman problem: selected algorithms and heuristics†
Spresser, D. M. (1989) · International Journal of Mathematical Education in Science and Technology · doi:10.1080/0020739890200605 · Cited by 3
A note on heuristics for the traveling salesman problem
d’Atri, G. (1980) · Mathematical Programming · doi:10.1007/bf01581633 · Cited by 3
Optimizing the experimental design of texture goniometry
Bachmann, F., Schaeben, H., & Hielscher, R. (2012) · Journal of Applied Crystallography · doi:10.1107/s0021889812041611 · Cited by 3
SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS
Li, K. (1997) · International Journal of Parallel Emergent and Distributed Systems · doi:10.1080/10637199708915622 · Cited by 3
Evaluation of Heuristic Algorithms for the TSP: A New Statistical Approach
Solis, R. (1984) · American Journal of Mathematical and Management Sciences · doi:10.1080/01966324.1984.10737138 · Cited by 3
Solving TSP based on Multi-Segment Multi-Orientation Nearest Neighbor algorithm
Zuo-Yong, X., Gao, X., Chen, Z., Liu-Bo, O., & Duan-lai, C. (2010) · IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS) · doi:10.1109/icicisys.2010.5658487 · Cited by 3
Ursani, Z., & Corne, D. (2016) · Journal of Optimization · doi:10.1155/2016/4786268 · Cited by 3
Cooperative receding horizon strategies for the multivehicle routing problem
Pietrabissa, A., Giorgio, A. D., Oddi, G., Chini, G., Chiang, M., & Poli, C. (2017) · Optimal Control Applications and Methods · doi:10.1002/oca.2345 · Cited by 3
Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics
Klootwijk, S., Manthey, B., & Visser, S. K. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-10564-8_9 · Cited by 3
HotFill : A cooling time constrained raster-fill planning algorithm for extrusion 3D printing
Nakonetchnei, E. C., Stolfi, J., Volpato, N., da Silva, R. D., & Minetto, R. (2022) · Advances in Engineering Software · doi:10.1016/j.advengsoft.2022.103219 · Cited by 3
Metodología de diseño y control de robots escaladores. Aplicación a las tareas de inspección
Giménez, A. (2011) · Tesis Doctorals en Xarxa (Consorci de Serveis Universitaris de Catalunya) · Cited by 3
Rodrigues, R. D. F. (1996) · doi:10.47749/t/unicamp.1996.108710 · Cited by 3
Chen, F., & Lu, C. (2008) · Encyclopedia of GIS · doi:10.1007/978-0-387-35973-1_865 · Cited by 3
Computer-Aided School Bus Routing for Rural Districts
Nygard, K. E., Summers, D. E., & Wagner, R. E. (1982) · AEDS Journal · doi:10.1080/00011037.1982.11008320 · Cited by 3
Pritchard, D., & Vempala, S. (2006) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1148109.1148155 · Cited by 3
The Two-Echelon Location Routing Problems: State of the Art, Models and Algorithms
Cuda, R. (2014) · Aisberg (University of Bergamo) · doi:10.13122/cuda-rosario_phd2014-02-07 · Cited by 3
Studies on probabilistic analysis of λ-opt for traveling salesperson problems
岡田, 正. (1999) · Institutional Repositories DataBase (IRDB) · doi:10.11501/3153830 · Cited by 3
NEW COMPUTATIONAL APPROACHES FOR THE TRANSPORTATION MODELS
Almaatani, D. E. (2014) · Lu Zone Ul (Laurentian University) · Cited by 3
An evaluation of solution-generating Algorithms for the asymmetric traveling salesman problem
McGuire, R. L. (1983) · OhioLink ETD Center (Ohio Library and Information Network) · Cited by 3
Lee, E. K., & Mitchell, J. E. (2001) · Springer eBooks · doi:10.1007/0-306-48332-7_214 · Cited by 3
Potvin, J. (1987) · doi:10.71781/33911 · Cited by 3
Routage et planification des personnels pour l'hospitalisation à domicile
Allaoua, H. (2014) · theses.fr (ABES) · doi:10.70675/358e3714za700z4dbcz804cz9a627bde5f24 · Cited by 3
Exploring Combinatorial Aspects of the Stop Number Problem
Colares, R. (2019) · theses.fr (ABES) · doi:10.70675/1a5cc40dz5aeez43ebzb7d3zbe6c57119b0b · Cited by 3
The traveling salesman problem in constraint programming
Isoart, N. (2021) · theses.fr (ABES) · doi:10.70675/782ee29azc160z4ea3z87f5ze4d8e6534463 · Cited by 3
Bertram, C. (2025) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.esa.2025.80 · Cited by 2
Integrating logistics planning and population sampling decisions for humanitarian needs assessment
Pamukçu, D., Çelik, M., & Balcik, B. (2025) · Socio-Economic Planning Sciences · doi:10.1016/j.seps.2025.102204 · Cited by 2
Capsule aggregated attention for vehicle routing problems
Ruiyang, S., Lingfeng, N., & Yu-Hong, D. (2024) · Scientia Sinica Mathematica · doi:10.1360/scm-2023-0307 · Cited by 2
Dordoy, S., Baxter, R., & Smith, A. D. (2026) · Journal of Experimental Psychology Learning Memory and Cognition · doi:10.1037/xlm0001573 · Cited by 2
A matheuristic and a hybrid algorithm for the asymmetric period travelling salesman problem
Henriques, S., & Paias, A. (2026) · European Journal of Operational Research · doi:10.1016/j.ejor.2026.02.009 · Cited by 2
Learning-Augmented Online Sorting and TSP
Bercea, I. O., Brodal, G. S., Iacono, J., Kozma, L., & Panigrahi, D. (2026) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.esa.2026.78 · Cited by 3
Bai, J., Zhang, L., Ran, J., & Li, X. R. (2026) · European Transport Research Review · doi:10.1186/s12544-026-00830-4 · Cited by 2
Online Metric TSP: Beyond the √n Barrier
Azar, Y., Panigrahi, D., & Vardi, O. (2026) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2026.18 · Cited by 2
On Scheduling in Distributed Transactional Memory: Techniques and Tradeoffs
Kim, J., Palmieri, R., & Ravindran, B. (2015) · Springer eBooks · doi:10.1007/978-1-4939-2092-1_44 · Cited by 2
Tendências de aplicações da otimização por colônia de formigas na progamação de JOB-SHOPS
de Freitas, F. F. T., & Vieira, G. E. (2009) · Revista Produção Online · doi:10.14488/1676-1901.v10i1.441 · Cited by 2
Advanced Bioinformatics Tools and Strategies
Hibbs, M. (2010) · Science Publishers eBooks · doi:10.1201/9781439845523-15 · Cited by 2
Heterogeneous Fleet Allocation and Route Planning Using Weighted Voronoi Diagrams
Yang, V. A., Dastoor, J., Wei, X., Bradley, J., Elghorab, M., Sudol, A., & Mavris, D. N. (2023) · AIAA SciTech Forum · doi:10.2514/6.2023-2706 · Cited by 2
An Iterative Optimization Algorithm for Planning Spacecraft Pathways Through Asteroids
Santucci, V. (2024) · Applied Sciences · doi:10.3390/app142310987 · Cited by 2
Informed Machine Learning Aspects for the Multi-Agent Neural Rewriter
Paul, N., Wirtz, T., Wrobel, S., & Kister, A. (2025) · Cognitive technologies · doi:10.1007/978-3-031-83097-6_11 · Cited by 2
Schulz, D., & Bauckhage, C. (2025) · Cognitive technologies · doi:10.1007/978-3-031-83097-6 · Cited by 2
Modular design capability and product positioning: An integrative view
Asan, U., & Polat, S. (2008) · Emerald Group Publishing Limited eBooks · doi:10.1016/s0749-6826(07)10002-0 · Cited by 2
Traveling Salesman Problem in a Geographic Information Management System
Santos, J. L., & Oliveira, A. F. M. D. A. (2020) · SEMA SIMAI Springer series · doi:10.1007/978-3-030-61844-5_8 · Cited by 2
An Algorithm Framework for Traveling Salesman Problem Using Geometric Information
Zhang, R., Qiu, J., Chen, X., & Guo, M. R. (2022) · Chinese Control and Decision Conference (CCDC) · doi:10.1109/ccdc55256.2022.10034033 · Cited by 2
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.