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 201–300 of 1,000
Komm, D., Kráľovič, R., Královič, R., & Smula, J. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-25258-2_23 · Cited by 37
Artificial intelligence approaches to network management: recent advances and a survey
Kumar, G. P., & Venkataram, P. (1997) · Computer Communications · doi:10.1016/s0140-3664(97)00094-7 · Cited by 37
Rationale, directions, and issues surrounding high speed networks
Chlamtac, I., & Franta, W. R. (1990) · Proceedings of the IEEE · doi:10.1109/5.52201 · Cited by 37
Flexible pair-copula estimation in D-vines using bivariate penalized splines
Kauermann, G., & Schellhase, C. (2013) · Statistics and Computing · doi:10.1007/s11222-013-9421-5 · Cited by 36
A Survey on Workforce Scheduling and Routing Problems
Castillo-Salazar, J. A., Landa-Silva, D., & Qu, R. (2012) · Repository@Nottingham (University of Nottingham) · Cited by 36
Heterogeneous Task Allocation and Sequencing via Decentralized Large Neighborhood Search
Sadeghi, A., & Smith, S. L. (2017) · Unmanned Systems · doi:10.1142/s2301385017500066 · Cited by 36
Modified Ant Colony Optimization with pheromone mutation for travelling salesman problem
Ratanavilisagul, C. (2017) · International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON) · doi:10.1109/ecticon.2017.8096261 · Cited by 36
Asymptotic expected performance of some TSP heuristics: An empirical evaluation
Ong, H. L., & Huang, H. C. (1989) · European Journal of Operational Research · doi:10.1016/0377-2217(89)90217-8 · Cited by 36
Krumke, S. O., MARATHE, M. V., Noltemeier, H., Radhakrishnan, V., Ravi, S. S., & Rosenkrantz, D. J. (1997) · Theoretical Computer Science · doi:10.1016/s0304-3975(96)00304-0 · Cited by 36
Self-citationTaouktsis, X., & Zikopoulos, C. (2023) · Expert Systems with Applications · doi:10.1016/j.eswa.2023.122010 · Cited by 35
Planning multi-goal tours for robot arms
Saha, M., Sanchez‐Ante, G., & Latombe, J.-C. (2004) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2003.1242179 · Cited by 35
Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
Jäger, G., & Molitor, P. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85097-7_20 · Cited by 35
Mapping planetary caves with an autonomous, heterogeneous robot team
Husain, A., Jones, H., Kannan, B., Wong, U. Y., Pimentel, T., Tang, S., Daftry, S., Huber, S., & Whittaker, W. (2013) · IEEE Aerospace Conference (AERO) · doi:10.1109/aero.2013.6497363 · Cited by 35
A ship-truck intermodal transportation problem
Infante, D., Paletta, G., & Vocaturo, F. (2009) · Maritime Economics & Logistics · doi:10.1057/mel.2009.6 · Cited by 35
Mobile Robots - State of the Art in Land, Sea, Air, and Collaborative Missions
Chen, X., Chen, Y., & Chase, J. G. (2009) · InTech eBooks · doi:10.5772/120 · Cited by 35
Restricted delivery problems on a network
Arkin, E. M., Hassin, R., & Klein, L. D. (1997) · Networks · doi:10.1002/(sici)1097-0037(199707)29:4<205::aid-net3>3.0.co;2-j · Cited by 35
Robust Wireless Rechargeable Sensor Networks
Yang, W., Lin, C., Dai, H., Wang, P., Ren, J., Wang, L., Wu, G., & Zhang, Q. (2022) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2022.3199389 · Cited by 34
The Online Graph Exploration Problem on Restricted Graphs
Miyazaki, S., Morimoto, N., & Okabe, Y. (2009) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.e92.d.1620 · Cited by 34
Hashimoto, H., Yagiura, M., Imahori, S., & Ibaraki, T. (2010) · 4OR · doi:10.1007/s10288-010-0144-6 · Cited by 34
An analysis of the extended Christofides heuristic for the -depot TSP
Xu, Z., Xu, L., & Rodrigues, B. (2011) · Operations Research Letters · doi:10.1016/j.orl.2011.03.002 · Cited by 34
Lower and upper competitive bounds for online directed graph exploration
Foerster, K.-T., & Wattenhofer, R. P. (2015) · Theoretical Computer Science · doi:10.1016/j.tcs.2015.11.017 · Cited by 34
Improving Ant Colony Optimization Algorithms for Solving Traveling Salesman Problems
Hung, K.-S., Su, S., & Lee, Z.-J. (2007) · Journal of Advanced Computational Intelligence and Intelligent Informatics · doi:10.20965/jaciii.2007.p0433 · Cited by 34
Network Service Chaining and Embedding With Provable Bounds
Zheng, D., Gu, H., Wei, W., Peng, C., & Cao, X. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.3038617 · Cited by 33
Baltz, A., Ouali, M. E., Jäger, G., Sauerland, V., & Srivastav, A. (2014) · Journal of the Operational Research Society · doi:10.1057/jors.2014.17 · Cited by 33
Adaptive PBDW Approach to State Estimation: Noisy Observations; User-Defined Update Spaces
Maday, Y., & Taddei, T. (2019) · SIAM Journal on Scientific Computing · doi:10.1137/18m116544x · Cited by 33
Scheduling reefer mechanics at container terminals
Hartmann, S. (2013) · Transportation Research Part E Logistics and Transportation Review · doi:10.1016/j.tre.2012.12.007 · Cited by 33
Modelagem heurística no problema de distribuição de cargas fracionadas de cimento.
Miura, M. (2008) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/d.3.2008.tde-17112008-115017 · Cited by 33
Cluster-based ensemble learning for wind power modeling from meteorological wind data
Chen, H. (2022) · Renewable and Sustainable Energy Reviews · doi:10.1016/j.rser.2022.112652 · Cited by 32
A scalable anticipatory policy for the dynamic pickup and delivery problem
Ghiani, G., Manni, A., & Manni, E. (2022) · Computers & Operations Research · doi:10.1016/j.cor.2022.105943 · Cited by 32
Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents
Disser, Y., Hackfeld, J., & Klimm, M. (2019) · Journal of the ACM · doi:10.1145/3356883 · Cited by 32
Liu, R., Yuan, B., & Jiang, Z. (2020) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2020.2964101 · Cited by 32
Scheduling of track inspection and maintenance activities in railroad networks
Peng, F. (2011) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 32
(Non)-Approximability for the Multi-criteria TSP(1,2)
Angel, É., Bampis, E., Gourvès, L., & Monnot, J. (2005) · Lecture notes in computer science · doi:10.1007/11537311_29 · Cited by 32
A multiperiod traveling salesman problem: Heuristic algorithms
Paletta, G. (1992) · Computers & Operations Research · doi:10.1016/0305-0548(92)90018-z · Cited by 32
Approximate greedy clustering and distance selection for graph metrics
Eppstein, D., Har-Peled, S., & Sidiropoulos, A. (2015) · Journal of computational geometry · doi:10.20382/jocg.v11i1a25 · Cited by 31
Financial stress relationships among Euro area countries: an R-vine copula approach
Zhang, D., Yan, M., & Tsopanakis, A. (2018) · European Journal of Finance · doi:10.1080/1351847x.2017.1419273 · Cited by 31
High-Coverage Point-to-Point Transit: Study of Path-Based Vehicle Routing Through Multiple Hubs
Jung, J., & Jayakrishnan, R. (2011) · Transportation Research Record Journal of the Transportation Research Board · doi:10.3141/2218-09 · Cited by 31
ARS: Automatic Routing Solver with Large Language ModelsPreprint
Li, K., Liu, F., Wang, Z., Tong, X., Han, X., Yuan, M., & Zhang, Q. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2502.15359 · Cited by 31
DIDES: a fast and effective sampling for clustering algorithm
Ros, F., & Guillaume, S. (2016) · Knowledge and Information Systems · doi:10.1007/s10115-016-0946-8 · Cited by 30
A framework for multi-robot node coverage in sensor networks
Gasparri, A., Krishnamachari, B., & Sukhatme, G. S. (2008) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/s10472-009-9126-9 · Cited by 30
A graph theoretic approach to utilizing protein structure to identify non-random somatic mutations
Ryslik, G., Cheng, Y., Cheung, K.-H., Modis, Y., & Zhao, H. (2014) · BMC Bioinformatics · doi:10.1186/1471-2105-15-86 · Cited by 30
ProTraS: A probabilistic traversing sampling algorithm
Ros, F., & Guillaume, S. (2018) · Expert Systems with Applications · doi:10.1016/j.eswa.2018.03.052 · Cited by 30
A Hierarchical Approach to Managing Dairy Routing
Adenso-Díaz, B., González, M., & García, E. (1998) · INFORMS Journal on Applied Analytics · doi:10.1287/inte.28.2.21 · Cited by 30
Li, W., Wang, C., Huang, Y. P., & Cheung, Y. (2022) · Applied Soft Computing · doi:10.1016/j.asoc.2022.109943 · Cited by 29
On Transactional Scheduling in Distributed Transactional Memory Systems
Kim, J., & Ravindran, B. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16023-3_29 · Cited by 29
Dynamic analysis of the arrow distributed protocol
Kühn, F., & Wattenhofer, R. P. (2004) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1007912.1007962 · Cited by 29
Survey of Methodologies for TSP and VRP
Anbuudayasankar, S. P., Ganesh, K., & Mohapatra, S. (2014) · Springer eBooks · doi:10.1007/978-3-319-05035-5_2 · Cited by 29
Ordered spatial sampling by means of the traveling salesman problem
Dickson, M. M., & Tillé, Y. (2016) · Computational Statistics · doi:10.1007/s00180-015-0635-1 · Cited by 29
Feature selection for distance-based regression: An umbrella review and a one-shot wrapper
Linja, J., Hämäläinen, J., Nieminen, P., & Kärkkäinen, T. (2022) · Neurocomputing · doi:10.1016/j.neucom.2022.11.023 · Cited by 28
Liśkiewicz, M., & Reischuk, R. (2005) · Lecture notes in computer science · doi:10.1007/11537311 · Cited by 28
Xu, Z., & Rodrigues, B. (2016) · European Journal of Operational Research · doi:10.1016/j.ejor.2016.08.054 · Cited by 28
Approximation Algorithms for Multi-Criteria Traveling Salesman Problems
Manthey, B., & Ram, L. S. (2007) · Algorithmica · doi:10.1007/s00453-007-9011-z · Cited by 28
Efficient heuristics for the design of ring networks
Gendreau, M., Labbé, M., & Laporte, G. (1995) · Telecommunication Systems · doi:10.1007/bf02110085 · Cited by 28
Dynamic programming based heuristics for the topological design of local access networks
Gouveia, L., & Paixão, J. M. P. (1991) · Annals of Operations Research · doi:10.1007/bf02071978 · Cited by 28
The cost-constrained traveling salesman problem
Sokkappa, P. R. (1990) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/6223080 · Cited by 28
Sui, J., Ding, S., Xia, B., Liu, R., & Bu, D. (2023) · Neural Computing and Applications · doi:10.1007/s00521-023-09042-6 · Cited by 27
Iantovics, L. B., Rotar, C., & Niazi, M. A. (2017) · International Journal of Intelligent Systems · doi:10.1002/int.21903 · Cited by 27
A real-time multicast routing algorithm for multimedia applications
Jia, X., Pissinou, N., & Makki, K. (1997) · Computer Communications · doi:10.1016/s0140-3664(97)00095-9 · Cited by 27
Ghiani, G., Guerriero, E., Manni, E., & Pareo, D. (2025) · Computers & Industrial Engineering · doi:10.1016/j.cie.2025.111001 · Cited by 26
Time window optimization for attended home service delivery under multiple sources of uncertainties
Yu, X., Shen, S., Badri-Koohi, B., & Seada, H. (2022) · Computers & Operations Research · doi:10.1016/j.cor.2022.106045 · Cited by 26
Kovač, M., Tadić, S. R., Krstić, M. D., & Veljović, M. (2023) · Mathematics · doi:10.3390/math11153347 · Cited by 26
Optimum path planning using convex hull and local search heuristic algorithms
Meeran, S., & Share, A. (1997) · Mechatronics · doi:10.1016/s0957-4158(97)00033-0 · Cited by 26
Silva, B. C. H., Fernandes, I. F. D. C., Goldbarg, M. C., & Goldbarg, E. F. G. (2020) · Computers & Operations Research · doi:10.1016/j.cor.2020.104950 · Cited by 26
Wang, Y., Li, J., Gao, K., & Pan, Q.-K. (2011) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2011.06.063 · Cited by 26
A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
Khan, M., & Pandurangan, G. (2006) · Lecture notes in computer science · doi:10.1007/11864219_25 · Cited by 26
The Traveling Salesman Problem
Körte, B., & Vygen, J. (2011) · Algorithms and combinatorics · doi:10.1007/978-3-642-24488-9_21 · Cited by 25
Genetic Algorithm for VRP with Constraints Based on Feasible Insertion
Vaira, G., & Kurasova, O. (2014) · Informatica · doi:10.15388/informatica.2014.09 · Cited by 25
Vine copulas and applications to the European Union sovereign debt analysis
Zhang, D. (2014) · International Review of Financial Analysis · doi:10.1016/j.irfa.2014.02.011 · Cited by 25
Route selection by rats and humans in a navigational traveling salesman problem
Blaser, R. E., & Ginchansky, R. R. (2011) · Animal Cognition · doi:10.1007/s10071-011-0449-7 · Cited by 25
A competitive analysis of algorithms for searching unknown scenes
Kalyanasundaram, B., & Pruhs, K. R. (1993) · Computational Geometry · doi:10.1016/0925-7721(93)90032-2 · Cited by 25
Fast Ergodic Search With Kernel Functions
Sun, M., Gaggar, A., Trautman, P., & Murphey, T. D. (2025) · IEEE Transactions on Robotics · doi:10.1109/tro.2025.3543298 · Cited by 24
Reordering Strategy for Blocking Optimization in Sparse Linear Solvers
Pichon, G., Faverge, M., Ramet, P., & Roman, J. (2017) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/16m1062454 · Cited by 24
Robot Path Planning for Dimensional Measurement in Automotive Manufacturing
Sheng, W., Xi, N., Song, M., & Chen, Y. (2005) · Journal of Manufacturing Science and Engineering · doi:10.1115/1.1870013 · Cited by 24
Tabu search algorithm based on insertion method
Fang, Y., Liu, G., He, Y., & Qiu, Y. (2003) · International Conference on Neural Networks and Signal Processing · doi:10.1109/icnnsp.2003.1279298 · Cited by 24
Charging Dynamic Sensors through Online Learning
Sun, Y., Lin, C., Yang, W. C., Ren, J., Wang, L., Wu, G., & Zhang, Q. (2023) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom53939.2023.10228955 · Cited by 23
Chen, W., Ke, J., & Chen, X. M. (2024) · Transportmetrica B Transport Dynamics · doi:10.1080/21680566.2024.2423235 · Cited by 23
Burning Graphs Through Farthest-First Traversal
García-Díaz, J., Pérez-Sansalvador, J. C., Rodríguez-Henríquez, L. M., & Cornejo-Acosta, J. A. (2022) · IEEE Access · doi:10.1109/access.2022.3159695 · Cited by 23
Online Graph Exploration: New Results on Old and New Algorithms
Megow, N., Mehlhorn, K., & Schweitzer, P. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22012-8_38 · Cited by 23
Mining fastest path from trajectories with multiple destinations in road networks
Lu, E. H.-C., Lee, W.-C., & Tseng, V. S. M. (2010) · Knowledge and Information Systems · doi:10.1007/s10115-010-0333-9 · Cited by 23
Lower Bounds for Insertion Methods for TSP
Azar, Y. (1994) · Combinatorics Probability Computing · doi:10.1017/s096354830000119x · Cited by 23
Worst-case analysis of two travelling salesman heuristics
Ong, H. L., & Moore, J. (1984) · Operations Research Letters · doi:10.1016/0167-6377(84)90078-6 · Cited by 23
copulaedas: AnRPackage for Estimation of Distribution Algorithms Based on Copulas
González-Fernández, Y., & Soto, M. (2014) · Journal of Statistical Software · doi:10.18637/jss.v058.i09 · Cited by 23
Investigating TSP Heuristics for Location-Based Services
Huang, W., & Yu, J. X. (2017) · Data Science and Engineering · doi:10.1007/s41019-016-0030-0 · Cited by 23
Good triangulations yield good tours
Letchford, A. N., & Pearson, N. A. (2006) · Computers & Operations Research · doi:10.1016/j.cor.2006.03.025 · Cited by 22
An improved lower bound for competitive graph exploration
Birx, A., Disser, Y., Hopp, A. V., & Karousatou, C. (2021) · Theoretical Computer Science · doi:10.1016/j.tcs.2021.04.003 · Cited by 22
A computerised vehicle routing system for refuse collection
Ong, H. L., Goh, T. N., Poh, K. L., & Lim, C. (1990) · Advances in Engineering Software (1978) · doi:10.1016/0141-1195(90)90019-3 · Cited by 22
Use of explicit memory in the dynamic traveling salesman problem
Tinós, R., Whitley, D., & Howe, A. E. (2014) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/2576768.2598247 · Cited by 22
Dynamic Vehicle Routing Problem with Multiple Depots
Meesuptaweekoon, K., & Chaovalitwongse, P. (2014) · Engineering Journal · doi:10.4186/ej.2014.18.4.135 · Cited by 22
Effective and Efficient: Large-Scale Dynamic City Express
Zhang, S., Qin, L., Zheng, Y., & Cheng, H. (2016) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2016.2604806 · Cited by 22
Rathore, H. (2016) · Springer eBooks · doi:10.1007/978-3-319-29782-8_7 · Cited by 22
Euclidean bounded-degree spanning tree ratios
Chan, T. M. (2003) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/777792.777795 · Cited by 22
Submodularity and the traveling salesman problem
Herer, Y. T. (1999) · European Journal of Operational Research · doi:10.1016/s0377-2217(98)00175-1 · Cited by 22
An algorithm for multicast tree generation in networks with asymmetric links
Ramanathan, S. (2002) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.1996.497911 · Cited by 22
Crowdsourced humanitarian relief vehicle routing problem
Parappathodi, J., & Archetti, C. (2022) · Computers & Operations Research · doi:10.1016/j.cor.2022.105963 · Cited by 21
A Neural-Network-Based Approach to the Double Traveling Salesman Problem
Plebe, A., & Anile, A. M. (2002) · Neural Computation · doi:10.1162/08997660252741194 · Cited by 21
A multi-criteria vehicle routing approach to improve the compliance audit schedule for food banks
Schneider, K., & Nurre, S. G. (2018) · Omega · doi:10.1016/j.omega.2018.05.002 · Cited by 21
A Comparison of ACO, GA and SA for Solving the TSP Problem
Valdez, F., Moreno, F., & Melín, P. (2019) · Studies in computational intelligence · doi:10.1007/978-3-030-34135-0_13 · Cited by 21
A fast Ant Colony Optimization for traveling salesman problem
Tseng, S.-P., Tsai, C., Chiang, M., & Yang, C. (2010) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2010.5586153 · Cited by 21
Moghtadernejad, S., Adey, B. T., & Hackl, J. (2022) · Journal of Infrastructure Systems · doi:10.1061/(asce)is.1943-555x.0000700 · Cited by 20
Foerster, K.-T., & Wattenhofer, R. P. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-35476-2_11 · Cited by 20
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.