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 501–600 of 1,000
Graph Exploration with Edge Weight EstimatesPreprint
Gehnen, M., Klasing, R., & Naquin, É. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2501.18496 · Cited by 7
RedAHD: Reduction-Based End-to-End Automatic Heuristic Design with Large Language ModelsPreprint
Thạch, N. N., Riahifar, A., Huynh, N. N., & Chan, H. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2505.20242 · Cited by 7
TIDE: Tuning-Integrated Dynamic Evolution for LLM-Based Automated Heuristic DesignPreprint
Chen, C., Zhong, M., Fan, Y., Shi, J., & Sun, J. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2601.21239 · Cited by 7
Sustainable risk mitigation in hazardous material transportation
Maio, A. D., Laporte, G., Musmanno, R., & Vocaturo, F. (2025) · Computers & Operations Research · doi:10.1016/j.cor.2025.107228 · Cited by 6
A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays
Dufay, M., & Wattenhofer, R. P. (2026) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611978971.144 · Cited by 6
Rasd: Semantic Shift Detection and Adaptation for Network Intrusion Detection
Alotaibi, F., & Maffeis, S. (2024) · IFIP advances in information and communication technology · doi:10.1007/978-3-031-65175-5_2 · Cited by 6
Cooperative agent navigation in partially unknown urban environments
Vokřínek, J., Komenda, A., & Pěchouček, M. (2010) · doi:10.1145/1967112.1967118 · Cited by 6
RILS: RFID indoor localization system using mobile readers
Liu, J., Qiu, Y., Yin, K., Dong, W., & Luo, J. (2018) · International Journal of Distributed Sensor Networks · doi:10.1177/1550147718771288 · Cited by 6
Algorithms for Euclidean Degree Bounded Spanning Tree Problems
Andersen, P., & Ras, C. (2019) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195919500031 · Cited by 6
Układanie tras pojazdów w łańcuchu dostaw. Modele, metody, zastosowania
Jadczak, R. (2019) · University of Lodz Repository (University of Łódź) · doi:10.18778/8142-140-9 · Cited by 6
Minimum Cycle Partition with Length Requirements
Hoppmann‐Baum, K., Mexi, G., Burdakov, O. P., Casselgren, C. J., & Koch, T. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-58942-4_18 · Cited by 6
Real-Time Auralisation of Outdoor Sound Propagation
Stienen, J. (2023) · Logos Verlag Berlin eBooks · doi:10.30819/5629 · Cited by 6
Multi-agent Online Graph Exploration on Cycles and Tadpole Graphs
van den Akker, E., Buchin, K., & Foerster, K.-T. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-60603-8_31 · Cited by 6
A Novel Ant Colony System Based on Minimum 1-Tree and Hybrid Mutation for TSP
Wang, C., Du-wu, C., Wang, Z., & Chen, D. (2005) · Lecture notes in computer science · doi:10.1007/11539117_168 · Cited by 6
Scalable Wireless Traffic Capture Through Community Detection and Trace Similarity
Sammarco, M., Campista, M. E. M., & de Amorim, M. D. (2015) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2015.2477809 · Cited by 6
Non-intrusive Monitoring of Stream Processing Applications
Vögler, M., Schleicher, J. M., Inzinger, C., Nickel, B., & Dustdar, S. (2016) · IEEE International Symposium on Service-Oriented System Engineering (SOSE) · doi:10.1109/sose.2016.11 · Cited by 6
Memory-based statistical learning for the travelling salesman problem
Xia, Y., & Li, C. (2016) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2016.7744160 · Cited by 6
Compatible Connectivity Augmentation of Planar Disconnected Graphs
Aloupis, G., Barba, L., Carmi, P., Dujmović, V., Frati, F., & Morin, P. (2015) · Discrete & Computational Geometry · doi:10.1007/s00454-015-9716-8 · Cited by 6
A dual local search framework for combinatorial optimization problems with TSP application
Ouenniche, J., Ramaswamy, P. K., & Gendreau, M. (2017) · Journal of the Operational Research Society · doi:10.1057/s41274-016-0173-4 · Cited by 6
Probe Machine Based Consecutive Route Filtering Approach to Symmetric Travelling Salesman Problem
Rahman, M. A., & Ma, J. (2018) · IFIP advances in information and communication technology · doi:10.1007/978-3-030-01313-4_41 · Cited by 6
Minimizing the average searching time for an object within a graph
Teller, R., Zofi, M., & Kaspi, M. (2019) · Computational Optimization and Applications · doi:10.1007/s10589-019-00121-w · Cited by 6
Li, H., & Wang, J. (2021) · International Conference on Intelligent Control and Information Processing · doi:10.1109/icicip53388.2021.9642212 · Cited by 6
Novel GA for metropolitan stations of Indian railways when modelled as a TSP
Deep, K., Mebrahtu, H., & Nagar, A. K. (2014) · International Journal of Systems Assurance Engineering and Management · doi:10.1007/s13198-014-0328-0 · Cited by 6
Planning fish scouting activity in industrial fishing
Millar, A. H. (1996) · Fisheries Research · doi:10.1016/0165-7836(95)00399-1 · Cited by 6
DeepBrowse: Similarity-Based Browsing Through Large Lists (Extended Abstract)
Chen, H., Anantharam, A. R., & Skiena, S. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-68474-1_21 · Cited by 6
Call-Based Dynamic Programming for the Precedence Constrained Line Traveling Salesman
Benoist, T., Jeanjean, A., & Jost, V. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-07046-9_1 · Cited by 6
CySpanningTree: Minimal Spanning Tree computation in Cytoscape
Shaik, F., Bezawada, S., & Goveas, N. (2015) · F1000Research · doi:10.12688/f1000research.6797.1 · Cited by 6
Job-shop Scheduling and Visibility Studies with a Hybrid ACO Algorithm
Heinonen, J., & Pettersson, F. (2007) · doi:10.5772/5113 · Cited by 6
Genetic coding for solving both the stacker crane problem and its k-variant
Zheng, L., & Zheng, W. (2002) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.1995.537910 · Cited by 6
Using global search heuristics for the capacity vehicle routing problem
Rodríguez, P., Nussbaum, M., Baeza, R. B., León, G., Sepúlveda, M., & Cobián, A. (1998) · Computers & Operations Research · doi:10.1016/s0305-0548(98)00045-8 · Cited by 6
Bertazzi, L., Paletta, G., & Speranza, M. G. (1999) · Lecture notes in economics and mathematical systems · doi:10.1007/978-3-642-58568-5_9 · Cited by 6
Remodeling the film copy deliverer problem
Zhang, L., & Zheng, W. (2002) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.1994.399895 · Cited by 6
Operations Research in Manufacturing
McCallum, C. J. (1986) · AT&T Technical Journal · doi:10.1002/j.1538-7305.1986.tb00461.x · Cited by 6
Optimization and Mechanism Design for Ridesharing Services
Lu, W. (2015) · OakTrust (Texas A&M University Libraries) · Cited by 6
Neural Online Graph ExplorationPreprint
Chiotellis, I., & Cremers, D. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.03345 · Cited by 6
A generic bee colony optimization framework for combinatorial optimization problems
Wong, L. P. (2012) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/48091 · Cited by 6
Simple Construction of Greedy Trees and Greedy PermutationsPreprint
Chubet, O., Sheehy, D. R., & Sheth, S. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2412.02554 · Cited by 6
Recent Advances in Routing Algorithms
Laporte, G. (1998) · Springer eBooks · doi:10.1007/978-3-662-03514-6_8 · Cited by 6
An improved upper bound for the online graph exploration problem on unicyclic graphs
Kobayashi, K., & Li, Y. (2024) · Journal of Combinatorial Optimization · doi:10.1007/s10878-024-01192-0 · Cited by 5
Optimal rebalancing and charging of shared electric scooters using charging hubs
Osorio, J., & Ouyang, Y. (2025) · Transportation Research Part E Logistics and Transportation Review · doi:10.1016/j.tre.2025.104018 · Cited by 5
Adaptive Charging With Beam Steering
Ren, M., Dai, H., Zhang, L., & Liu, T. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3579692 · Cited by 5
Zhao, S., & Duan, Q. (2026) · Mathematics · doi:10.3390/math14010166 · Cited by 5
Perepelkin, D. A., & Nguyen, T. (2022) · Mediterranean Conference on Embedded Computing (MECO) · doi:10.1109/meco55406.2022.9797090 · Cited by 5
Kim, G., Jin, H., Kim, M., Jang, K., & Jang, I. G. (2023) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2023.3271313 · Cited by 5
Learning-based TSP-solvers tend to be overly greedy
Li, X., & Zhang, S. (2026) · Computers & Operations Research · doi:10.1016/j.cor.2026.107467 · Cited by 5
A Populated Iterated Greedy Algorithm with Inver-Over Operator for Traveling Salesman Problem
Tasgetiren, M. F., Büyükdağlı, Ö., Kızılay, D., & Karabulut, K. (2013) · Lecture notes in computer science · doi:10.1007/978-3-319-03753-0_1 · Cited by 5
Yeh, T.-S., & Chiang, T.-C. (2018) · IEEE International Conference on Industrial Engineering and Engineering Management (IEEM) · doi:10.1109/ieem.2018.8607486 · Cited by 5
Multi-level Heuristic to Optimize the Chemotherapy Production and Delivery
Robbes, A., Kergosien, Y., & Billaut, J. (2020) · Springer proceedings in mathematics & statistics · doi:10.1007/978-3-030-39694-7_21 · Cited by 5
An Efficient Hybrid Genetic Algorithm for the Quadratic Traveling Salesman Problem
Pham, Q. A., Lau, H. C., Hà, M. H., & Vu, L. (2023) · Proceedings of the International Conference on Automated Planning and Scheduling · doi:10.1609/icaps.v33i1.27212 · Cited by 5
Effective Parallelization of the Vehicle Routing Problem
Muniasamy, R. P., Singh, S., Nasre, R., & Narayanaswamy, N. S. (2023) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/3583131.3590458 · Cited by 5
A Lower Bound for the Max Entropy Algorithm for TSP
Jin, B., Klein, N., & Williamson, D. P. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-59835-7_18 · Cited by 5
Demonstrating conceptual dynamics in an evolving text collection
Darányi, S., & Wittek, P. (2013) · Journal of the American Society for Information Science and Technology · doi:10.1002/asi.22940 · Cited by 5
Rutas de recogida de muestras y error en el proceso analítico
Belles‐Sampera, J., Pedret, S. V., Castellvi, M. G., & March-Amengual, J.-M. (2011) · Revista del Laboratorio Clínico · doi:10.1016/j.labcli.2011.09.002 · Cited by 5
Receding horizon multi-vehicle routing for emergency scenarios
Chini, G., Poli, C., Oddi, G., Pietrabissa, A., & Grigioni, M. (2014) · Mediterranean Conference on Control and Automation (MED) · doi:10.1109/med.2014.6961400 · Cited by 5
Visual heuristics for data clustering
Tran-Luu, T.-D., & DeClaris, N. (2002) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.1997.625712 · Cited by 5
Gotta (efficiently) catch them all: Pokémon GO meets Orienteering Problems
Álvarez‐Miranda, E., Luipersbeck, M., & Sinnl, M. (2017) · European Journal of Operational Research · doi:10.1016/j.ejor.2017.08.012 · Cited by 5
Two-Stage Heuristic Algorithm Proposal for Urban E-Commerce Deliveries
Karaoğlu, M., & Kara, G. (2021) · Asia Pacific Journal of Operational Research · doi:10.1142/s0217595921500342 · Cited by 5
Graphon estimation via nearest‐neighbour algorithm and two‐dimensional fused‐lasso denoising
Padilla, O. H. M., & Chen, Y. (2021) · Canadian Journal of Statistics · doi:10.1002/cjs.11676 · Cited by 5
Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation
Herráiz, Á. C., Gutiérrez, M., & Ortega-Mier, M. (2021) · Central European Journal of Operations Research · doi:10.1007/s10100-021-00784-z · Cited by 5
A convex hull cheapest insertion heuristic for the non-Euclidean TSP
Goutham, M., Rosati, E. D., Schuler, H., Menon, M., Garrow, S., & Stockar, S. (2026) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2026.105685 · Cited by 5
Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio
Deǐneko, V. G., & Tiskin, A. (2009) · Electronic Notes in Discrete Mathematics · doi:10.1016/j.endm.2009.02.004 · Cited by 5
Chung, S. H., Pearn, W. L., & Tai, Y. T. (2008) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2602604 · Cited by 5
A geometric problem involving the nearest neighbour algorithm
Meir, A. (1987) · Operations Research Letters · doi:10.1016/0167-6377(87)90045-9 · Cited by 5
Probabilistic analysis of optimization problems on generalized random shortest path metrics
Klootwijk, S., Manthey, B., & Visser, S. K. (2021) · Theoretical Computer Science · doi:10.1016/j.tcs.2021.03.016 · Cited by 5
Comparison of eleven measures for estimating difficulty of open-loop TSP instances
Sengupta, L., & Fränti, P. (2021) · Applied Computing and Intelligence · doi:10.3934/aci.2021001 · Cited by 5
Fast upper and lower bounds for a large‐scale real‐world arc routing problem
Boyacı, B., Dang, T. H., & Letchford, A. N. (2022) · Networks · doi:10.1002/net.22120 · Cited by 5
Sign depth tests in multiple regression
Horn, M., & Müller, C. H. (2022) · Journal of Statistical Computation and Simulation · doi:10.1080/00949655.2022.2130922 · Cited by 5
Datta, A. K. (2015) · Information Processing Letters · doi:10.1016/j.ipl.2015.06.009 · Cited by 5
An Improved Ant Colony Algorithm for Path Optimization in Emergency Rescue
Jin, B., & Zhang, L. (2010) · International Workshop on Intelligent Systems and Applications (ISA) · doi:10.1109/iwisa.2010.5473427 · Cited by 5
Efficient Visualization of Large-Scale Data Tables through Reordering and Entropy Minimization
Djuric, N., & Vučetić, S. (2013) · Proceedings · doi:10.1109/icdm.2013.63 · Cited by 5
Maximum travelling salesman problem
Котов, В. М., & Kovalev, M. M. (1996) · Mathematical Methods of Operations Research · doi:10.1007/bf01680370 · Cited by 5
Compact storage schemes for formatted files by spanning trees
Ernvall, J., & Nevalainen, O. (1979) · BIT Numerical Mathematics · doi:10.1007/bf01931262 · Cited by 5
Greedy randomized adaptive search procedure for traveling salesman problem
Lee, S. H. (2006) · OakTrust (Texas A&M University Libraries) · Cited by 5
Near-Optimal Path Planning for Complex Robotic Inspection TasksPreprint
Bogaerts, B., Sels, S., Vanlanduit, S., & Penne, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.05528 · Cited by 5
Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of CostsPreprint
Paul, N., Wirtz, T., Wrobel, S., & Kister, A. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2206.05990 · Cited by 5
Sign depth for parameter tests in multiple regression
Horn, M. (2021) · Technische Universität Dortmund Eldorado (Technische Universität Dortmund) · doi:10.17877/de290r-22355 · Cited by 5
Algorithmic contributions to qualitative constraint-based spatial and temporal reasoning
Sioutis, M. (2017) · theses.fr (ABES) · doi:10.70675/d83a70b4zce22z478az9370z6b5e0da5330f · Cited by 5
Wang, J., Fu, H., Han, Z., Jin, H., Zhang, P., & Sun, S. (2024) · Polymer Composites · doi:10.1002/pc.29073 · Cited by 4
Zhang, K., Xu, X., & Zhao, M. (2025) · Mathematics · doi:10.3390/math13121934 · Cited by 4
Efficient bit labeling in factorization machines with annealing for traveling salesman problem
Koshikawa, S., Hosaka, A., & Yoshida, T. (2025) · Scientific Reports · doi:10.1038/s41598-025-10064-4 · Cited by 4
Machine learning intermolecular electronic couplings: Opportunities and challenges
Wang, C.-I., Lindsay, A. C., & Jackson, N. E. (2025) · APL Computational Physics · doi:10.1063/5.0297213 · Cited by 4
Gradient guided furthest point sampling for robust training set selection
Trestman, M. M., Gugler, S., Faber, F. A., & von Lilienfeld, O. A. (2026) · Machine Learning Science and Technology · doi:10.1088/2632-2153/ae68b8 · Cited by 4
Utilizing Multipath Effects for Mobile Charging
Gao, J., Wu, D., Zhang, L., Li, J., Yang, J. Q., Peng, J., & Liu, T. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3557899 · Cited by 4
Roberts-Elliott, L., Das, G. P., & Cielniak, G. (2025) · Robotics · doi:10.3390/robotics14060077 · Cited by 4
Generating practical last-mile delivery routes using a data-informed insertion heuristic
Rashidi, H., Nourinejad, M., & Roorda, M. J. (2025) · Transportation Research Part C Emerging Technologies · doi:10.1016/j.trc.2025.105278 · Cited by 4
Adawiyah, R. A., Satria, Y., & Burhan, H. (2019) · Journal of Physics Conference Series · doi:10.1088/1742-6596/1218/1/012008 · Cited by 4
Ratanavilisagul, C. (2021) · IEEE International Conference on Computer and Communications (ICCC) · doi:10.1109/iccc54389.2021.9674689 · Cited by 4
Truly tight bounds for TSP heuristics
Hurkens, C. A. J. (2023) · Operations Research Letters · doi:10.1016/j.orl.2023.06.003 · Cited by 4
A Decomposition-Based Hybrid Algorithm for Multi-objective Vehicle Routing Problem with Time Windows
Wang, Y., Liu, F., & Zhang, Q. (2023) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec53210.2023.10254116 · Cited by 4
Sensor Path Planning and Scheduling for Aircraft Emergency Landing Field Monitoring
Nospes, D., & Stütz, P. (2024) · IEEE Aerospace Conference (AERO) · doi:10.1109/aero58975.2024.10521099 · Cited by 4
Marginal Effect-aware Multiple-Vehicle Scheduling for Road Data Collection: A Near-optimal Result
Cheng, W., Jiang, Z., Xiang, C., & Fu, J. (2024) · ACM Transactions on Sensor Networks · doi:10.1145/3679016 · Cited by 4
Optimising AGV Routing in Container Terminals: Nearest Neighbor vs. Tabu Search
Puška, A., Bosna, J., Petrović, N., & Marković, S. (2024) · Mechatronics and intelligent transportation systems · doi:10.56578/mits030401 · Cited by 4
Zhang, L., He, Z., Zhu, H., Wei, Z., Lu, J., & He, X. (2025) · Agronomy · doi:10.3390/agronomy15051230 · Cited by 4
ODES: Online Domain Adaptation with Expert Guidance for Medical Image Segmentation
Islam, M. S., Nag, S., Dutta, A., Ahmed, S. M., Niloy, F. F., Bera, S., & Roy–Chowdhury, A. K. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-04965-0_34 · Cited by 4
Solving the Green Vehicle Routing Problem with Capacitated Alternative Fuel Stations
Bruglieri, M., Mancini, S., & Pisacane, O. (2019) · Virtual Community of Pathological Anatomy (University of Castilla La Mancha) · Cited by 4
The Optimization of Pastry Delivery for NOPEK Bakery in Vysoké Mýto
Kucera, P., & Jarkovská, M. (2010) · Agris on-line Papers in Economics and Informatics · doi:10.22004/ag.econ.99088 · Cited by 4
Online Network Design with Outliers
Anagnostopoulos, A., Grandoni, F., Leonardi, S., & Sankowski, P. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14165-2_11 · Cited by 4
Tsai, Y. T., & Tang, C. Y. (1993) · Information Processing Letters · doi:10.1016/0020-0190(93)90142-v · Cited by 4
Optimal spatial monitoring of populations described by reaction-diffusion models
Parisey, N., Leclerc, M., & Adamczyk-Chauvat, K. (2021) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2021.110976 · Cited by 4
Efficient procedure planning for comprehensive lymph node staging bronchoscopy
Kuhlengel, T. K., Bascom, R., & Higgins, W. E. (2022) · Journal of medical imaging · doi:10.1117/1.jmi.9.5.055001 · Cited by 4
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.