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 701–800 of 1,000
Schröder, K., Kastius, A., & Schlößer, R. (2026) · The Knowledge Engineering Review · doi:10.48130/ker-0026-0001 · Cited by 2
Google earth engine based monitoring spatio-temporal variability of Kızılırmak River plume
Dihkan, M., & Hamzaoglu, C. (2025) · International Journal of Environmental Science and Technology · doi:10.1007/s13762-025-06462-w · Cited by 2
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise
Künnemann, M., Manthey, B., & Veenstra, R. (2025) · Algorithmica · doi:10.1007/s00453-025-01335-7 · Cited by 2
Industrial application of the Bipartite TSP in robotic pick-and-place operations
Giannakos, K., Tsakoumis, D., Plitsos, S., Koronakos, G., Vivo, G., & Eirinakis, P. (2025) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2025.09.236 · Cited by 2
Traversability in Spatial Configuration: Some Theoretical and Practical Aspects
Li, C., Psarra, S., & Hanna, S. (2024) · UCL Discovery (University College London) · Cited by 2
On some single-machine scheduling with sequence-dependent set-up times
Zhang, L., & Zheng, W. (2002) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.1996.571250 · Cited by 2
A knowledge-based system for ATM network management
Chen, J.-L., Sun, H.-F., Tsai, C.-H., & Wu, C.-Y. (2002) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.1994.399896 · Cited by 2
Oscillated Variable Neighborhood Search for Open Vehicle Routing Problem
Güler, B., & Şevkli, A. Z. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-26555-1_21 · Cited by 2
Özsoyoǧlu, Z. M. (2012) · ACM Transactions on Database Systems · doi:10.1145/2338626.2338627 · Cited by 2
Rada, R. (1981) · Biosystems · doi:10.1016/0303-2647(81)90071-x · Cited by 2
A Very Large Scale Neighborhood (Vlsn) Search Algorithm for an Inventory-Routing Problem
Sindhuchao, S. (2006) · Science & Technology Asia · Cited by 2
On the Effect of Adding Nodes to TSP Instances: An Empirical Analysis
Crişan, G. C., Nechita, E., & Palade, V. (2016) · Intelligent systems reference library · doi:10.1007/978-3-319-46200-4_2 · Cited by 2
Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems
Ravi, R., MARATHE, M. V., Ravi, S. S., Rosenkrantz, D. J., & Hunt, H. B. (2009) · Springer eBooks · doi:10.1007/978-1-4020-9688-4_9 · Cited by 2
Self-citationA new approach based on graph matching and evolutionary approach for sport scheduling problem
Khelifa, M., Boughaci, D., & Aïmeur, E. (2020) · Intelligent Decision Technologies · doi:10.3233/idt-190114 · Cited by 2
Evasive Navigation of an Autonomous Mobile Robot in Hostile Unknown Environments
Veksler, Y., & Rimon, E. (2021) · Springer proceedings in advanced robotics · doi:10.1007/978-3-030-66723-8_4 · Cited by 2
Extremely Fast “Solution” to the Large-Scale and Very Large-Scale Vehicle Routing Problem
Riechel, J. (2021) · International Journal of Transportation Engineering and Technology · doi:10.11648/j.ijtet.20210704.12 · Cited by 2
On a Traveling Salesman Problem with Dynamic Obstacles and Integrated Motion Planning
Hellander, A., & Axehill, D. (2022) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc53348.2022.9867369 · Cited by 2
Approximations for the Steiner Multicycle problem
Fernandes, C. G., Lintzmayer, C. N., & Moura, P. F. S. (2024) · Theoretical Computer Science · doi:10.1016/j.tcs.2024.114836 · Cited by 2
Protocol Test Sequence Generation Using MUIOS Based on TSP Problem
Kumar, G. P., & Venkataram, P. (1995) · Springer eBooks · doi:10.1007/978-0-387-34887-2_10 · Cited by 2
The Euclidian Traveling Salesman Selection Problem
Hamacher, A., & Moll, C. (1996) · Operations research proceedings · doi:10.1007/978-3-642-80117-4_10 · Cited by 2
The Unreasonable Success of Local Search: Geometric OptimizationPreprint
Cohen-Addad, V., & Mathieu, C. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1410.0553 · Cited by 2
Noga, M. T. (1984) · VTechWorks (Virginia Tech) · Cited by 2
Heurísticas para o problema de distribuição com estoques geridos pelo fornecedor.
Znamensky, A. (2006) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/t.3.2006.tde-13122006-175235 · Cited by 2
Jeromin, B., & Körker, F. (1986) · Optimization · doi:10.1080/02331938608843104 · Cited by 2
Lenstra, J. K., Kan, A. H. G. R., & Boas, V. P. E. (1978) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · Cited by 2
Diseño óptimo de rutas para una empresa que brinda servicios de paquetería, mensajería y logística.
Porras, Á., & Angélica, D. (2014) · El Repositorio Academico Digital de la UANL (Universidad Autónoma de Nuevo León) · Cited by 2
Determinação de percursos de corte numa fábrica de ferramentas de alta precisão
Moreira, L. M. N. S. A. (2001) · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) · doi:10.34626/5nec-vt63 · Cited by 2
Meta-heuristics for the multiple trip vehicle routing problem with backhauls
Wassan, N. (2016) · Kent Academic Repository (University of Kent) · Cited by 2
Maximizing the probability of arriving on time : a stochastic shortest path problem
Cao, Z. (2017) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/69617 · Cited by 2
Fast minimum-weight double-tree shortcutting for Metric TSP: Is the best one good enough?Preprint
Deǐneko, V. G., & Tiskin, A. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0710.0318 · Cited by 2
Multicrossover genetic algorithms for combinatorial optimisation problems
Lee, L. S. (2006) · ePrints Soton (University of Southampton) · Cited by 2
EKO: Adaptive Sampling of Compressed Video DataPreprint
Bang, J., Chunduri, P., & Arulraj, J. J. P. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.01671 · Cited by 2
Furneaux, A. (2021) · Kent Academic Repository (University of Kent) · doi:10.22024/unikent/01.02.89043 · Cited by 3
5/4 approximation for Symmetric TSPPreprint
Chauhan, A., & Verma, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.05291 · Cited by 2
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian NoisePreprint
Künnemann, M., Manthey, B., & Veenstra, R. (2023) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.48550/arxiv.2308.00306 · Cited by 2
Brinkmann, J. (2023) · Springer eBooks · doi:10.1007/978-3-031-16536-8_3 · Cited by 2
Learning to Generate Hard Instances: Towards Robust Solutions for Vehicle Routing ProblemsPreprint
Jiang, X., Wu, Y., & Zhang, Y. (2024) · doi:10.36227/techrxiv.171261343.36084709/v1 · Cited by 2
Generating Practical Last-mile Delivery Routes using a Data-informed Insertion HeuristicPreprint
Rashidi, H., Nourinejad, M., & Roorda, M. J. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4828958 · Cited by 2
Generating Practical Last-mile Delivery Routes using a Data-informed Insertion HeuristicPreprint
Rashidi, H., Nourinejad, M., & Roorda, M. J. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4830661 · Cited by 2
A comparison of two effective methods for reordering columns within supernodesPreprint
Karsavuran, M. O., Ng, E., & Peyton, B. W. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2501.08395 · Cited by 2
regAL: Python package for active learning of regression problems
Surzhikova, E., & Proppe, J. (2025) · Machine Learning Science and Technology · doi:10.1088/2632-2153/addf11 · Cited by 2
Tests based on sign depth for multiple regression
Horn, M., & Müller, C. H. (2020) · Technische Universität Dortmund Eldorado (Technische Universität Dortmund) · doi:10.17877/de290r-20984 · Cited by 2
Burkhalter, M., Moghtadernejad, S., Hackl, J., Concepcion, T.-D., Moli Diaz, A. A., Martani, C., Adey, B. T., Jimenez–Redondo, N., Pardi, L., Gennaro, F. D., et al. (2020) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-b-000503443 · Cited by 2
A Differential Evolution Algorithm for Generic Combinatorial Optimization Problems
Ali, I. (2020) · UNSWorks (University of New South Wales, Sydney, Australia) · doi:10.26190/unsworks/3968 · Cited by 2
Game-Theoretic Co-Evolution for LLM-Based Heuristic DiscoveryPreprint
Ke, X., Li, K., Xing, J., Zhang, Y., & Cheng, J. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2601.22896 · Cited by 2
Recherche à voisinage variable pour des problèmes de routage avec ou sans gestion de stock
Mjirda, A. (2014) · theses.fr (ABES) · doi:10.70675/78d012d5z8011z4f0eza205zac156145bd71 · Cited by 2
Planification de la recharge et optimisation des tournées dans le cas de flottes captives
Sassi, O. (2015) · theses.fr (ABES) · doi:10.70675/33b64b8fz5529z419ez9ff1z2bf201011187 · Cited by 2
Optimisation de problème de tournées de véhicules de service à domicile
Liu, Y. (2017) · theses.fr (ABES) · doi:10.70675/8625efffza74fz45b9z8a20z4719cb3a0a21 · Cited by 2
RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional ExperiencePreprint
Wu, Y., Pan, J., Zhang, Y., Xu, N., Zeng, F., & Cheng, J. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.11358 · Cited by 2
Randomization Helps in Online Graph Exploration: Breaking the Deterministic Lower Bound on CyclesPreprint
Baligács, J., Hązła, J., & Volk, L. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.11203 · Cited by 2
Studies on local search-based approaches for vehicle routing and scheduling problems
Hashimoto, H. (2008) · Institutional Repositories DataBase (IRDB) · doi:10.14989/doctor.k13987 · Cited by 2
Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
D’Andrea, A., Forlizzi, L., & Proietti, G. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-98355-4_10 · Cited by 1
TSP review: performance comparison of the well-known methods on a standardized dataset
Akhmetov, I., & Pak, A. (2023) · International Asian School-Seminar Optimization Problems of Complex Systems (OPCS) · doi:10.1109/opcs59592.2023.10275749 · Cited by 1
UAVs for Sustainable Palm Oil Production: An Ant Colony Approach to Efficient Path Planning
Lai, W. K., Pak Hen, C. H. E. N., Li Li, L. I. M., & Patrick Sheng Siang, L. E. E. (2024) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/smc54092.2024.10830939 · Cited by 1
Yu, Z., Ma, Y., Chen, F.-D., & Wang, L. (2025) · Communications in computer and information science · doi:10.1007/978-981-96-9955-1_10 · Cited by 1
Decoupled Training Neural Solver for Dynamic Traveling Salesman Problem
Lin, S., Cui, H., Wang, Y., & Jia, Y.-H. (2025) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra55743.2025.11128415 · Cited by 1
A Note on the Largest Insertion Algorithm for the Traveling Salesman Problem
Ostuni, D., & Righini, G. (2025) · Networks · doi:10.1002/net.70012 · Cited by 1
Er, C. İ., Kashiri, A., & Yazıcıoğlu, Y. (2026) · Journal of Intelligent & Robotic Systems · doi:10.1007/s10846-026-02426-5 · Cited by 1
Kaleta, M., & Śliwiński, T. (2025) · International Conference on Control, Decision and Information Technologies (CoDIT) · doi:10.1109/codit66093.2025.11321536 · Cited by 1
Traffic-Informed Optimization of Last-Mile Delivery Using Hybrid Heuristic Approaches
Yeboah, A. S., Chimba, D., & Rohit, M. (2026) · Future Transportation · doi:10.3390/futuretransp6020055 · Cited by 1
Learning Semantic Priorities for Autonomous Target Search
Lodel, M., Wilde, N., Babuška, R., & Alonso–Mora, J. (2026) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra57385.2026.11697522 · Cited by 1
Vaaras, E., Airaksinen, M., & Räsänen, O. J. (2026) · Computers in Biology and Medicine · doi:10.1016/j.compbiomed.2026.111809 · Cited by 1
STEM: Semantic target search and exploration using MAVs in cluttered environments
Sethi, N., Lodel, M., Ferranti, L., Babuška, R., & Alonso–Mora, J. (2026) · Autonomous Robots · doi:10.1007/s10514-026-10247-6 · Cited by 1
Li, Y., Zhou, Y., Juan, R., Wang, T. H., Li, Z., Liu, S., Shi, S., & Gao, Z. (2026) · Advanced Engineering Informatics · doi:10.1016/j.aei.2026.104968 · Cited by 1
ConvIO: A Framework for Convergence of Inputs and Outputs in Automotive Zonal E/E Architectures
Mauser, L., Patil, H., Patiño-Studencka, L., & Wagner, S. (2026) · IEEE Access · doi:10.1109/access.2026.3707952 · Cited by 1
Robot-assisted energy-efficient data collection from high-fidelity sensor networks
Tinta, S. P., Yu, Z., & Wong, J. L. (2009) · IEEE International Conference on Technologies for Practical Robot Applications · doi:10.1109/tepra.2009.5339637 · Cited by 1
Basic techniques for design and analysis of algorithms
Reingold, E. M. (1996) · ACM Computing Surveys · doi:10.1145/234313.234321 · Cited by 1
Guimarães, T. A., Scarpin, C. T., & Steiner, M. T. A. (2014) · Advanced materials research · doi:10.4028/www.scientific.net/amr.945-949.3219 · Cited by 1
Wittek, P. (2013) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2013.03.026 · Cited by 1
Utilizing traveling—Salesman subtours to create sales districts
Feiring, B. R. (1986) · Engineering Costs and Production Economics · doi:10.1016/s0167-188x(86)80003-9 · Cited by 1
Çelikbilek, C. (2016) · OhioLink ETD Center (Ohio Library and Information Network) · Cited by 1
Algorithmic Approaches for Solving Hard Problems: Approximation and Complexity
Mömke, T. (2009) · OPUS (Augsburg University) · doi:10.3929/ethz-a-005981139 · Cited by 1
A Subgradient Method to Improve Approximation Ratio in the Minimum Latency Problem
Ban, H.-B., & Duc, N. N. (2013) · Advances in intelligent systems and computing · doi:10.1007/978-3-319-02741-8_29 · Cited by 1
TETRAHEURÍSTICA SISTÉMICA (THS) PARA EL TSP
Rave, J. I. P., Jaramillo, P., Mesa, C. M. P., & Velásquez, L. F. M. (2010) · Ingeniare. Revista chilena de ingeniería · doi:10.4067/s0718-33052010000200006 · Cited by 1
The Design and Implementation of A Cost-effective RFID Indoor Localization System
Luo, J., Zhou, S., Cheng, H., Liao, Y., & Guo, B. (2015) · doi:10.1145/2820716.2820718 · Cited by 1
Analysis of two Sweep-line Algorithms for Constructing Spanning Trees and Steiner Trees
Dumitrescu, A., & Tóth, C. D. (2007) · JUCS - Journal of Universal Computer Science · doi:10.3217/jucs-013-11-1615 · Cited by 1
Ramdass, K. R., & Masithulela, F. (2015) · The South African Journal of Industrial Engineering · doi:10.7166/26-3-1252 · Cited by 1
Nouaouri, I., Gonçalves, G., & Jolly, D. (2011) · INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING RESEARCH AND DEVELOPMENT · doi:10.34218/ijierd.2.1.2011.007 · Cited by 1
Miki, M., Hiroyasu, T., Hanada, Y., & Mizuta, T. (2003) · Transactions of the Institute of Systems Control and Information Engineers · doi:10.5687/iscie.16.607 · Cited by 1
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0012 · Cited by 1
Counting, Sampling, and Statistical Physics
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0013 · Cited by 1
When Formulas Freeze: Phase Transitions in Computation
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0014 · Cited by 1
Approximation algorithms for constructing spanning K-trees using stock pieces of bounded length
Lichen, J., Li, J., & Lih, K. (2016) · Optimization Letters · doi:10.1007/s11590-016-1078-5 · Cited by 1
An Adaptive Large Neighborhood Search Heuristic for the Inventory Routing Problem with Time Windows
Hadianniasar, M. (2015) · Journal of the Arkansas Academy of Science · Cited by 1
An upper bound for the shortest hamiltonian path in the symmetric euclidean case
Tomescu, I. (1983) · RAIRO - Operations Research · doi:10.1051/ro/1983170302971 · Cited by 1
Incremental Matrix Reordering for Similarity-Based Dynamic Data Sets
Rastin, P., & Mateï, B. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70139-4_8 · Cited by 1
Routing for Balanced Logistics
Anbuudayasankar, S. P., Ganesh, K., & Mohapatra, S. (2014) · Springer eBooks · doi:10.1007/978-3-319-05035-5_3 · Cited by 1
Optimization-Based Spatial Positioning and Energy Management for Unmanned Aerial Vehicles
Martin, R. E. (2018) · ScholarsArchive (Brigham Young University) · Cited by 1
Depot Location Problems By Considering Its Distribution Problems
Sartika, H., & Gamal, M. D. H. (2019) · Journal of Research in Mathematics Trends and Technology · doi:10.32734/jormtt.v1i1.753 · Cited by 1
A Memetic Algorithm for the Team Orienteering Problem
Trachanatzi, D., Tsakirakis, E., Marinaki, M., Marinakis, Y., & Matsatsinis, N. F. (2019) · Springer eBooks · doi:10.1007/978-3-030-06222-4_14 · Cited by 1
LOGÍSTICA PARA O RECOLHIMENTO DE FRUTAS: UM ESTUDO DE CASO
Ribeiro, J. F. F., Ribeiro, L. C., & Siquitelli, C. V. D. A. (2019) · Revista Latino-Americana de Inovação e Engenharia de Produção · doi:10.5380/relainep.v7i11.66092 · Cited by 1
THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
Aldous, D. (2021) · Probability in the Engineering and Informational Sciences · doi:10.1017/s0269964821000115 · Cited by 1
“Incremental” Evaluation for Genetic Crossover
Pitzer, E., & Affenzeller, M. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-45093-9_48 · Cited by 1
GENERATOR FUEL COST OPTIMIZATION USING ANT COLONY ALGORITHM
Suryawati, I., & Rochman, S. (2019) · BEST Journal of Applied Electrical Science & Technology · doi:10.36456/best.vol1.no1.1988 · Cited by 1
Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics
Klootwijk, S., & Manthey, B. (2020) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.aofa.2020.19 · Cited by 1
Dynamic programming for the electric vehicle orienteering problem with multiple technologies
Bezzi, D., Ceselli, A., & Righini, G. (2018) · Archivio Istituzionale della Ricerca (Universita Degli Studi Di Milano) · Cited by 1
Insertion heuristics for central cycle problems
Lamb, J. D. (2009) · Networks · doi:10.1002/net.20348 · Cited by 1
Special Issue of Sustainable Asia Conference 2014
Choi, Y., & Zhang, N. (2018) · MDPI eBooks · doi:10.3390/books978-3-03897-110-8 · Cited by 1
Lin, J., Zeng, X., Liu, J., & Li, K. (2021) · Journal of Combinatorial Optimization · doi:10.1007/s10878-021-00759-5 · Cited by 1
Scheduling of Mobile Charger with Multiple Antennas
Li, L., Zhao, Y., Dai, H., Wang, X., & Chen, G. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-86130-8_1 · Cited by 1
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.