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 401–500 of 1,000
Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks
Ghodselahi, A., & Kühn, F. (2017) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.disc.2017.22 · Cited by 12
Al-Badri, A. M., Bargooth, A. F., Al-Jebori, J. G. A., & Zegyer, E. A. K. (2019) · Veterinary World · doi:10.14202/vetworld.2019.1372-1377 · Cited by 12
Efficient heuristics to minimize the total tardiness of chemotherapy drug production and delivery
Robbes, A., Kergosien, Y., André, V., & Billaut, J. (2021) · Flexible Services and Manufacturing Journal · doi:10.1007/s10696-021-09431-w · Cited by 12
Weighted nearest neighbor algorithms for the graph exploration problem on cycles
Asahiro, Y., Miyano, E., Miyazaki, S., & Yoshimuta, T. (2009) · Information Processing Letters · doi:10.1016/j.ipl.2009.10.013 · Cited by 12
Vine Estimation of Distribution Algorithms with Application to Molecular Docking
Soto, M., Ochoa, A., González-Fernández, Y., Milanés, Y., Álvarez, A., Carrera, D., & Moreno, E. (2012) · Adaptation, learning, and optimization · doi:10.1007/978-3-642-28900-2_13 · Cited by 12
The Traveling Salesman Problem
Maquin, D. (2005) · Springer eBooks · doi:10.1007/3-540-29297-7_21 · Cited by 12
Practical aspects of route planning for magazine and newspaper wholesalers
Dillmann, R., Becker, B., & Beckefeld, V. (1996) · European Journal of Operational Research · doi:10.1016/0377-2217(95)00191-3 · Cited by 12
Pichon, G. (2018) · theses.fr (ABES) · doi:10.70675/f03dcd69za905z4dc5za2d4zd420c3f7370f · Cited by 12
Scheduling Closed-Nested Transactions in Distributed Transactional Memory
Kim, J., & Ravindran, B. (2012) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2012.26 · Cited by 11
A Comparative Study of the Some Methods Used in Constructing Coresets for Clustering Large Datasets
Hoang, N. L., Trang, L. H., & Dang, T. K. (2020) · SN Computer Science · doi:10.1007/s42979-020-00227-7 · Cited by 11
Recycling Wasted Energy for Mobile Charging
Sun, Y., Lin, C., Dai, H., Wang, P., Ren, J., Wang, L., & Wu, G. (2021) · IEEE International Conference on Network Protocols (ICNP) · doi:10.1109/icnp52444.2021.9651967 · Cited by 11
Prakash, S., & Mukherjee, I. (2023) · Journal of Cleaner Production · doi:10.1016/j.jclepro.2023.138212 · Cited by 11
Kyritsis, M., Gulliver, S. R., Feredoes, E. A., & Din, S. U. (2018) · Cognitive Systems Research · doi:10.1016/j.cogsys.2018.07.027 · Cited by 11
Kovács, L., Iantovics, L. B., & Iakovidis, D. K. (2018) · Symmetry · doi:10.3390/sym10120663 · Cited by 11
Approximation algorithms for process systems engineering
Letsios, D., Baltean-Lugojan, R., Ceccon, F., Mistry, M., Wiebe, J., & Misener, R. (2019) · Computers & Chemical Engineering · doi:10.1016/j.compchemeng.2019.106599 · Cited by 11
On the approximation ratio of the 3-Opt algorithm for the (1,2)-TSP
Zhong, X. (2021) · Operations Research Letters · doi:10.1016/j.orl.2021.05.012 · Cited by 11
Blaser, R. E., & Wilber, J. (2012) · Psychological Research · doi:10.1007/s00426-012-0470-8 · Cited by 11
Temporal bounded reasoning in a dynamic case based planning agent for industrial environments
Navarro, M., Paz, J. F. D., Julián, V., Rodríguez, S., Bajo, J., & Corchado, J. M. (2012) · Expert Systems with Applications · doi:10.1016/j.eswa.2012.01.119 · Cited by 11
Bordenave, C., Foss, S., & Last, G. (2011) · Queueing Systems · doi:10.1007/s11134-011-9246-x · Cited by 11
Vine copula classifiers for the mind reading problem
Carrera, D., Santana, R., & Lozano, J. A. (2016) · Progress in Artificial Intelligence · doi:10.1007/s13748-016-0095-z · Cited by 11
On the Integration of a TSP Heuristic into an EA for the Bi-objective Ring Star Problem
Liefooghe, A., Jourdan, L., Jozefowiez, N., & Talbi, E. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88439-2_9 · Cited by 11
Reducing Channel Density in Standard Cell Layout
Supowit, K. J. (1983) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac.1983.1585660 · Cited by 11
Integer Programming: Branch and Bound Methods
Lee, E. K., & Mitchell, J. E. (2008) · Springer eBooks · doi:10.1007/978-0-387-74759-0_286 · Cited by 11
Goel, L., Vaishnav, G., Ramola, S. C., & Purohit, T. (2023) · IETE Technical Review · doi:10.1080/02564602.2023.2167742 · Cited by 10
A Hybrid Brain Storm Optimization Algorithm for Dynamic Vehicle Routing Problem With Time Windows
Liu, M., Zhao, Q. G., Song, Q., & Zhang, Y. (2023) · IEEE Access · doi:10.1109/access.2023.3328404 · Cited by 10
Geiger, A. (2024) · Computers & Industrial Engineering · doi:10.1016/j.cie.2024.110455 · Cited by 10
Instance-Specific Parameter Tuning for Meta-Heuristics
Ries, J., Beullens, P., & Wang, Y. (2013) · IGI Global eBooks · doi:10.4018/978-1-4666-2086-5.ch005 · Cited by 10
Khan, M., Pandurangan, G., & Kumar, V. S. A. (2007) · Theoretical Computer Science · doi:10.1016/j.tcs.2007.05.028 · Cited by 10
M3: Microscope-based maskless micropatterning with dry film photoresist
Leigh, S. Y., Tattu, A., Mitchell, J. S. B., & Entcheva, E. G. (2010) · Biomedical Microdevices · doi:10.1007/s10544-010-9506-2 · Cited by 10
Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem
Warburton, A. (1993) · Operations Research Letters · doi:10.1016/0167-6377(93)90082-r · Cited by 10
Fast Minimum-Weight Double-Tree Shortcutting for Metric TSP
Deǐneko, V. G., & Tiskin, A. (2007) · Springer eBooks · doi:10.1007/978-3-540-72845-0_11 · Cited by 10
Explanations for combinatorial optimization problems
Erwig, M., & Kumar, P. (2024) · Journal of Computer Languages · doi:10.1016/j.cola.2024.101272 · Cited by 9
Olsen, C. C., Kalyanam, K., Baker, W. P., & Kunz, D. L. (2019) · Unmanned Systems · doi:10.1142/s2301385019500079 · Cited by 9
A Framework of Ant Colony P System
Luo, Y., Guo, P., & Zhang, M. (2019) · IEEE Access · doi:10.1109/access.2019.2949952 · Cited by 9
Ying, K., & Lin, S.-W. (2020) · PLoS ONE · doi:10.1371/journal.pone.0240628 · Cited by 9
On the Routing of Unmanned Aerial Vehicles (UAVs) in Precision Farming Sampling Missions
Dolias, G., Benos, L. T., & Bochtis, D. (2022) · Springer optimization and its applications · doi:10.1007/978-3-030-84152-2_5 · Cited by 9
Variable neighbourhood structures for cycle location problems
Lamb, J. D. (2012) · European Journal of Operational Research · doi:10.1016/j.ejor.2012.05.038 · Cited by 9
Thermal sensor design for 3D ICs
Kashfi, F., & Draper, J. (2012) · IEEE International Midwest Symposium on Circuits and Systems (MWSCAS) · doi:10.1109/mwscas.2012.6292062 · Cited by 9
The processing time optimization of printed circuit board
Ancău, M. (2009) · Circuit World · doi:10.1108/03056120910979512 · Cited by 9
Assisted navigation for large information spaces
Dennis, B. M., & Healey, C. G. (2003) · Visualization · doi:10.1109/visual.2002.1183803 · Cited by 9
Pardalos, P. M., & Li, Y. (1993) · Handbook of statistics · doi:10.1016/s0169-7161(05)80132-4 · Cited by 9
A microcomputer assistant for the development of vehicle routing and scheduling heuristics
Potvin, J., Lapalme, G., & Rousseau, J. M. (1994) · Decision Support Systems · doi:10.1016/0167-9236(94)90073-6 · Cited by 9
A Case Study in Applied Algorithm Design
Bentley, J. L. (1984) · Computer · doi:10.1109/mc.1984.1659058 · Cited by 9
Landscape-Aware Bandit Hyper-Heuristics for Online Operator Selection in UAV Inspection RoutingPreprint
Junhao, W., Li, Y., Zhao, Y., He, Q., Li, H., 姚德兴, Lu, B., Peng, Z., Wang, Y., Im, S.-K., et al. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2605.14620 · Cited by 9
Length-constrained cycle partition with an application to UAV routing*
Hoppmann‐Baum, K., Burdakov, O. P., Mexi, G., Casselgren, C. J., & Koch, T. (2022) · Optimization methods & software · doi:10.1080/10556788.2022.2053972 · Cited by 8
Efficient Coverage Path Planning for a Drone in an Urban Environment
Sabag, J., Pinkovich, B., Rivlin, E., & Rotstein, H. P. (2025) · Drones · doi:10.3390/drones9020098 · Cited by 8
Asgharyar, M., Farmand, N., & Shetab-Boushehri, S.-N. (2025) · Computers & Operations Research · doi:10.1016/j.cor.2025.107048 · Cited by 8
Maya-López, A., Casino, F., & Solanas, A. (2021) · Symmetry · doi:10.3390/sym13060916 · Cited by 8
Heuristics for a cash-collection routing problem with a cluster-first route-second approach
Singh, B., Oberfichtner, L., & Ivliev, S. A. (2022) · Annals of Operations Research · doi:10.1007/s10479-022-04883-1 · Cited by 8
Nemoto, T., Niitsuma, N., & Kamamichi, N. (2024) · Smart Agricultural Technology · doi:10.1016/j.atech.2024.100450 · Cited by 8
Improving combinatorial auctions for multi-robot exploration
Cavalcante, R. C., Noronha, T. F., & Chaimowicz, L. (2013) · International Conference on Advanced Robotics (ICAR) · doi:10.1109/icar.2013.6766508 · Cited by 8
Computational Intelligence and Combinatorial Optimization Problems in Transportation Science
Kritikos, M. N., & Lappas, P. Z. (2020) · Learning and analytics in intelligent systems · doi:10.1007/978-3-030-41196-1_15 · Cited by 8
Wang, X., Wang, S., Bi, D., & Liang, D. (2007) · Sensors · doi:10.3390/s7112693 · Cited by 8
Approximation result toward nearest neighbor heuristic
Monnot, J. (2002) · Yugoslav journal of operations research · doi:10.2298/yjor0201011m · Cited by 8
Path Planning Strategy of Autonomous Climbing Robot for Inspection Applications in Construction
Balaguer, C., Padrón, V., Giménez, A. M., Pastor, J. M., & Abderrahim, M. (1999) · International Symposium on Automation and Robotics in Construction (ISARC) · doi:10.22260/isarc1999/0053 · Cited by 8
A Public Vehicle System with Multiple Origin-Destination Pairs on Traffic Networks
Zhu, M., Kong, L., Liu, X.-Y., Shen, R., Shu, W., & Wu, M. (2014) · Globecom · doi:10.1109/glocom.2014.7417469 · Cited by 8
Fast and effective reordering of columns within supernodes using partition refinement
Jacquelin, M., Ng, E., & Peyton, B. W. (2018) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975215.8 · Cited by 8
Approximation Algorithms for Multi-criteria Traveling Salesman Problems
Manthey, B., & Ram, L. S. (2007) · Lecture notes in computer science · doi:10.1007/11970125_24 · Cited by 8
Mao, L.-J., Deo, N., & Lang, S.-D. (2003) · International Symposium on Pervasive Systems, Algorithms and Networks (ISPAN) · doi:10.1109/ispan.1999.778937 · Cited by 8
Verweij, B., & Aardal, K. (2003) · Mathematical Programming · doi:10.1007/s10107-002-0321-2 · Cited by 8
Global strategies for augmenting the efficiency of TSP heuristics
Codenotti, B., Manzini, G., Margara, L., & Resta, G. (1993) · Lecture notes in computer science · doi:10.1007/3-540-57155-8_253 · Cited by 8
Worst-Case Analysis of Heuristic Algorithms for Scheduling and Packing
Fisher, M. L. (1982) · Springer eBooks · doi:10.1007/978-94-009-7801-0_2 · Cited by 8
A Scheme for Batch Verification of Integrity Assertions in a Database System
Lilien, L. T., & Bhargava, B. (1984) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1984.5010295 · Cited by 8
Efficient multicast tree algorithm in ATM networks
Jia, X., Lee, C. H., Makki, K., & Pissinou, N. (1996) · Computer Communications · doi:10.1016/s0140-3664(96)01095-x · Cited by 8
Леонтьев, В. К. (1981) · Journal of Mathematical Sciences · doi:10.1007/bf01084282 · Cited by 8
Pritchard, D. (2005) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 7
The complexity of Nash Equilibria, Local Optima, and Pareto-Optimal solutions
Röglin, H., & Vöcking, B. (2008) · RWTH Publications (RWTH Aachen) · Cited by 8
Competitive analysis of the online dial-a-ride problem
Birx, A. (2020) · TUbilio (Technical University of Darmstadt) · doi:10.25534/tuprints-00014134 · Cited by 8
On the Recoverable Traveling Salesman ProblemPreprint
Goerigk, M., Lendl, S., & Wulf, L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.09691 · Cited by 8
Reordering strategy for blocking optimization in sparse linear solvers
Pichon, G., Faverge, M., Ramet, P., & Roman, J. (2016) · HAL · Cited by 8
Multi-Objective Infeasibility Diagnosis for Routing Problems Using Large Language ModelsPreprint
Li, K., Zheng, R., Hao, X., & Wang, Z. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2508.03406 · Cited by 8
AHD Agent: Agentic Reinforcement Learning for Automatic Heuristic DesignPreprint
Lv, H., Lu, N., Zhou, Z., Ong, Y.-S., & Liu, S. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2605.08756 · Cited by 8
Tjandra, S. S., Setiawan, F., & Salsabila, H. (2022) · Jurnal Optimasi Sistem Industri · doi:10.25077/josi.v21.n2.p75-86.2022 · Cited by 7
Heterogeneous Coverage Path Planning for Multi-Agent Systems with ACO and GA
Bahabadi, M. H. J., Mahdavi, A., & Khankalantary, S. (2024) · doi:10.1109/icee63041.2024.10667967 · Cited by 7
A Sparse Multicover Bifiltration of Linear Size
Alonso, Á. J. (2026) · Discrete & Computational Geometry · doi:10.1007/s00454-026-00865-3 · Cited by 7
Through-Wall Mobile Charging: Theory, Methodology, and Implementation
Sun, Y., Lin, C., Yang, W., Dai, H., Ren, J., Wang, L., & Wu, G. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3527440 · Cited by 7
Exploiting Edited Large Language Models as General Scientific Optimizers
Lv, Q., Liu, T., & Wang, H. (2025) · Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT) · doi:10.18653/v1/2025.naacl-long.270 · Cited by 7
Atomizer: Beyond Non‐Planar Slicing for Fused Filament Fabrication
Chermain, X., Cocco, G., Zanni, C., Garner, E., Hugron, P.-A., & Lefèbvre, S. (2025) · Computer Graphics Forum · doi:10.1111/cgf.70189 · Cited by 7
Exploration of graphs with excluded minors
Baligács, J., Disser, Y., Heinrich, I., & Schweitzer, P. (2025) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2025.103725 · Cited by 7
Ground Tactical Mission Support by Multi-agent Control of UAV Operations
Vokřínek, J., Novák, P., & Komenda, A. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23181-0_22 · Cited by 7
Bakshi, S., Yan, Z., Chen, D., Qian, Q., & Chen, Y. (2018) · Journal of Dynamic Systems Measurement and Control · doi:10.1115/1.4040665 · Cited by 7
Service Function Chaining and Embedding with Spanning Closed Walk
Zheng, D., Peng, C., Liao, X., Luo, G., Tian, L., & Cao, X. (2019) · IEEE International Conference on High Performance Switching and Routing (HPSR) · doi:10.1109/hpsr.2019.8808131 · Cited by 7
Quasi-linear time heuristic to solve the Euclidean traveling salesman problem with low gap
Formella, A. (2024) · Journal of Computational Science · doi:10.1016/j.jocs.2024.102424 · Cited by 7
Quantum Local Search for Traveling Salesman Problem with Path-Slicing Strategy
Liu, C.-Y., Matsuyama, H., Huang, W., & Yamashiro, Y. (2025) · International Conference on Quantum Communications, Networking, and Computing (QCNC) · doi:10.1109/qcnc64685.2025.00110 · Cited by 7
Körner, F. (1986) · European Journal of Operational Research · doi:10.1016/0377-2217(86)90188-8 · Cited by 7
Xie, K., Liu, Z., Chen, N., & Chen, T. (2021) · Genomics Proteomics & Bioinformatics · doi:10.1016/j.gpb.2020.06.014 · Cited by 7
Integrated Planning of Operational Maintenance Programs for Water and Gas Distribution Networks
Kerwin, S. M., & Adey, B. T. (2021) · Journal of Infrastructure Systems · doi:10.1061/(asce)is.1943-555x.0000646 · Cited by 7
An Adaptive Hybrid Quantum Algorithm for the Metric Traveling Salesman Problem
Li, F., & Mazumder, A. R. (2023) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps54959.2023.00082 · Cited by 7
Wong, L., Khader, A. T., Al‐Betar, M. A., & Tan, T.-P. (2013) · International Conference on Intelligent Systems Design and Applications (ISDA) · doi:10.1109/isda.2013.6920757 · Cited by 7
The Metric Travelling Salesman Problem: The Experiment on Pareto-optimal Algorithms
Avdoshin, S. M., & Beresneva, E. (2017) · Proceedings of the Institute for System Programming of RAS · doi:10.15514/ispras-2017-29(4)-8 · Cited by 7
Trachanatzi, D., Rigakis, M., Marinaki, M., Marinakis, Y., & Matsatsinis, N. F. (2019) · Soft Computing · doi:10.1007/s00500-019-04438-w · Cited by 7
Fast minimum-weight double-tree shortcutting for metric TSP: Is the best one good enough?
Deǐneko, V. G., & Tiskin, A. (2009) · ACM Journal of Experimental Algorithmics · doi:10.1145/1498698.1594232 · Cited by 7
Modeling 3D synthetic view dissimilarity
Zhao, S., & Ooi, W. T. (2015) · The Visual Computer · doi:10.1007/s00371-015-1069-z · Cited by 7
Bewertung heuristischer Methoden
Pfohl, H., & Hebel, R. (1982) · Mathematical Methods of Operations Research · doi:10.1007/bf01917133 · Cited by 7
IMPROVING LOCAL SEARCH FOR THE TRAVELING SALESMAN PROBLEM
Misevičius, A., Ostreika, A., Šimaitis, A., & Žilevičius, V. (2007) · Information Technology And Control · doi:10.5755/j01.itc.36.2.11839 · Cited by 7
Kalyanasundaram, B., & Pruhs, K. R. (1992) · Lecture notes in computer science · doi:10.1007/3-540-55210-3_180 · Cited by 7
Altınkemer, K., & Pirkul, H. (1992) · Journal of Information and Optimization Sciences · doi:10.1080/02522667.1992.10699092 · Cited by 7
The L1 traveling salesman problem
Allison, D. C. S., & Noga, M. T. (1984) · Information Processing Letters · doi:10.1016/0020-0190(84)90110-8 · Cited by 7
On the refinement of bounds of heuristic algorithms for the traveling salesman problem
Jeromin, B., & Körner, F. (1985) · Mathematical Programming · doi:10.1007/bf01585662 · Cited by 7
Heuristic and Metaheuristic Algorithms for the Traveling Salesman Problem
Marinakis, Y. (2024) · Springer eBooks · doi:10.1007/978-3-030-54621-2_262-1 · Cited by 7
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.