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
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
Ant colony system: a cooperative learning approach to the traveling salesman problem
Dorigo, M., & Gambardella, L. M. (1997) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.585892 · Cited by 8,081
Voronoi diagrams—a survey of a fundamental geometric data structure
Aurenhammer, F. (1991) · ACM Computing Surveys · doi:10.1145/116873.116880 · Cited by 4,340
An effective implementation of the Lin–Kernighan traveling salesman heuristic
Helsgaun, K. (2000) · European Journal of Operational Research · doi:10.1016/s0377-2217(99)00284-2 · Cited by 1,630
Complexity of vehicle routing and scheduling problems
Lenstra, J. K., & Kan, A. H. G. R. (1981) · Networks · doi:10.1002/net.3230110211 · Cited by 1,325
Optimization Approaches for the Traveling Salesman Problem with Drone
Agatz, N., Bouman, P., & Schmidt, M. (2018) · Transportation Science · doi:10.1287/trsc.2017.0791 · Cited by 1,029
The traveling salesman problem: An overview of exact and approximate algorithms
Laporte, G. (1992) · European Journal of Operational Research · doi:10.1016/0377-2217(92)90138-y · Cited by 971
Routing and scheduling of vehicles and crews
Raff, S. (1983) · Computers & Operations Research · doi:10.1016/0305-0548(83)90030-8 · Cited by 867
Skiena, S. S. (2008) · Springer eBooks · doi:10.1007/978-1-84800-070-4 · Cited by 706
Revealing the vectors of cellular identity with single-cell genomics
Wagner, A., Regev, A., & Yosef, N. (2016) · Nature Biotechnology · doi:10.1038/nbt.3711 · Cited by 632
The electric vehicle routing problem with nonlinear charging function
Montoya, A., Guéret, C., Mendoza, J. E., & Villegas, J. G. (2017) · Transportation Research Part B: Methodological · doi:10.1016/j.trb.2017.02.004 · Cited by 627
Review of job shop scheduling research and its new perspectives under Industry 4.0
Zhang, J., Ding, G., Zou, Y., Qin, S., & Fu, J. (2019) · Journal of Intelligent Manufacturing · doi:10.1007/s10845-017-1350-2 · Cited by 558
The selective travelling salesman problem
Laporte, G., & Martello, S. (1990) · Discrete Applied Mathematics · doi:10.1016/0166-218x(90)90100-q · Cited by 507
Genetic algorithms for the traveling salesman problem
Potvin, J. (1996) · Annals of Operations Research · doi:10.1007/bf02125403 · Cited by 503
Combined location-routing problems: A synthesis and future research directions
Min, H., Jayaraman, V., & Srivastava, R. (1998) · European Journal of Operational Research · doi:10.1016/s0377-2217(97)00172-0 · Cited by 486
Geometric Shortest Paths and Network Optimization
Mitchell, J. S. B. (2000) · Handbook of Computational Geometry · doi:10.1016/b978-044482537-7/50016-4 · Cited by 427
Campbell, A. M., Vandenbussche, D., & Hermann, W. (2008) · Transportation Science · doi:10.1287/trsc.1070.0209 · Cited by 413
Local optimization and the Traveling Salesman Problem
Johnson, D. S. (2005) · Springer eBooks · doi:10.1007/bfb0032050 · Cited by 406
Voronoi Diagrams**Partially supported by the Deutsche Forschungsgemeinschaft, grant K1 655 2-2.
Aurenhammer, F., & Klein, R. (2000) · Handbook of Computational Geometry · doi:10.1016/b978-044482537-7/50006-1 · Cited by 392
Getting Things in Order: An Introduction to the R Package seriation
Hahsler, M., Hornik, K., & Buchta, C. (2008) · Journal of Statistical Software · doi:10.18637/jss.v025.i03 · Cited by 385
Solving the Orienteering Problem through Branch-and-Cut
Fischetti, M., Salazar‐González, J., & Toth, P. (1998) · INFORMS journal on computing · doi:10.1287/ijoc.10.2.133 · Cited by 380
Routing to Multiple Destinations in Computer Networks
Bharath-Kumar, K., & Jaffe, J. M. (1983) · IRE Transactions on Communications Systems · doi:10.1109/tcom.1983.1095818 · Cited by 366
Approximation algorithms for the geometric covering salesman problem
Arkin, E. M., & Hassin, R. (1994) · Discrete Applied Mathematics · doi:10.1016/0166-218x(94)90008-6 · Cited by 356
The Traveling Salesman Problem and its Variations
Monnot, J., & Toulouse, S. (2014) · Wiley eBooks · doi:10.1002/9781119005353.ch7 · Cited by 356
Imase, M., & Waxman, B. M. (1991) · SIAM Journal on Discrete Mathematics · doi:10.1137/0404033 · Cited by 354
Edge crossings in drawings of bipartite graphs
Eades, P., & Wormald, N. (1994) · Algorithmica · doi:10.1007/bf01187020 · Cited by 349
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems
Campbell, A. M., & Savelsbergh, M. W. P. (2004) · Transportation Science · doi:10.1287/trsc.1030.0046 · Cited by 312
New Algorithms for Bin Packing
Yao, A. C.-C. (1980) · Journal of the ACM · doi:10.1145/322186.322187 · Cited by 281
Coverage path planning of heterogeneous unmanned aerial vehicles based on ant colony system
Chen, J., Ling, F., Zhang, Y., You, T., Liu, Y., & Du, X. (2022) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2021.101005 · Cited by 279
Waiting strategies for the dynamic pickup and delivery problem with time windows
Mitrović-Minić, S., & Laporte, G. (2003) · Transportation Research Part B Methodological · doi:10.1016/j.trb.2003.09.002 · Cited by 264
A multi-objective optimization approach to urban school bus routing: Formulation and solution method
Bowerman, R. L., Hall, B., & Calamai, P. H. (1995) · Transportation Research Part A Policy and Practice · doi:10.1016/0965-8564(94)e0006-u · Cited by 263
Heuristic analysis, linear programming and branch and bound
Wolsey, L. A. (1980) · Mathematical programming studies · doi:10.1007/bfb0120913 · Cited by 253
Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms
Fredman, M. L., & Tarjan, R. E. (2005) · 25th Annual Symposium onFoundations of Computer Science, 1984. · doi:10.1109/sfcs.1984.715934 · Cited by 247
A tabu search heuristic for the undirected selective travelling salesman problem
Gendreau, M., Laporte, G., & Semet, F. (1998) · European Journal of Operational Research · doi:10.1016/s0377-2217(97)00289-0 · Cited by 243
An immunity-based ant colony optimization algorithm for solving weapon–target assignment problem
Lee, Z.-J., Lee, C.-Y., & Su, S.-F. (2002) · Applied Soft Computing · doi:10.1016/s1568-4946(02)00027-3 · Cited by 235
Deterministic Order-Up-To Level Policies in an Inventory Routing Problem
Bertazzi, L., Paletta, G., & Speranza, M. G. (2002) · Transportation Science · doi:10.1287/trsc.36.1.119.573 · Cited by 234
An Adaptive Clustering-Based Algorithm for Automatic Path Planning of Heterogeneous UAVs
Chen, J., Zhang, Y., Wu, L., You, T., & Ning, X. (2021) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2021.3131473 · Cited by 232
Chapter 4 The traveling salesman problem
Jünger, M., Reinelt, G., & Rinaldi, G. (1995) · Handbooks in Operations Research and Management Science · doi:10.1016/s0927-0507(05)80121-5 · Cited by 230
Wang, D., Hu, P., Du, J., Zhou, P., Deng, T., & Hu, M. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2939397 · Cited by 217
Machine learning for the structure–energy–property landscapes of molecular crystals
Musil, F., De, S., Yang, J., Campbell, J. E., Day, G. M., & Ceriotti, M. (2018) · Chemical Science · doi:10.1039/c7sc04665k · Cited by 216
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
Englert, M., Röglin, H., & Vöcking, B. (2013) · Algorithmica · doi:10.1007/s00453-013-9801-4 · Cited by 207
The Travelling Salesman Problem with pick-up and delivery
Mosheiov, G. (1994) · European Journal of Operational Research · doi:10.1016/0377-2217(94)90360-3 · Cited by 190
Topological design of telecommunication networks-local access design methods
Gavish, B. (1991) · Annals of Operations Research · doi:10.1007/bf02061657 · Cited by 184
A model for warehouse order picking
Daniels, R. L., Rummel, J. L., & Schantz, R. H. (1998) · European Journal of Operational Research · doi:10.1016/s0377-2217(97)00043-x · Cited by 184
Multicast tree generation in networks with asymmetric links
Ramanathan, S. (1996) · IEEE/ACM Transactions on Networking · doi:10.1109/90.532865 · Cited by 184
Minimum-weight two-connected spanning networks
Monma, C. L., Munson, B. S., & Pulleyblank, W. R. (1990) · Mathematical Programming · doi:10.1007/bf01585735 · Cited by 180
Atom-density representations for machine learning
Willatt, M. J., Musil, F., & Ceriotti, M. (2019) · The Journal of Chemical Physics · doi:10.1063/1.5090481 · Cited by 179
Reconstructing cell cycle pseudo time-series via single-cell transcriptome data
Liu, Z., Lou, H., Xie, K., Wang, H., Chen, N., Aparicio, O. M., Zhang, M. Q., Jiang, R., & Chen, T. (2017) · Nature Communications · doi:10.1038/s41467-017-00039-z · Cited by 155
Many birds with one stone: multi-objective approximation algorithms
Ravi, R., MARATHE, M. V., Ravi, S. S., Rosenkrantz, D. J., & Hunt, H. B. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167209 · Cited by 174
Self-citationNguyen, T. T., Székely, E., Imbalzano, G., Behler, J., Csányi, G., Ceriotti, M., Götz, A. W., & Paesani, F. (2018) · The Journal of Chemical Physics · doi:10.1063/1.5024577 · Cited by 171
Attention, Learn to Solve Routing Problems!
Kool, W., van Hoof, H., & Welling, M. (2018) · UvA-DARE (University of Amsterdam) · doi:10.48550/arxiv.1803.08475 · Cited by 171
Oscope identifies oscillatory genes in unsynchronized single-cell RNA-seq experiments
Leng, N., Chu, L.-F., Barry, C., Li, Y., Choi, J., Li, X., Jiang, P., Stewart, R. M., Thomson, J. A., & Kendziorski, C. (2015) · Nature Methods · doi:10.1038/nmeth.3549 · Cited by 170
Optimal Lines in Public Rail Transport
Bussieck, M. R. (1998) · Digitale Bibliothek Braunschweig (Verbundzentrale Göttingen (VZG)) · doi:10.24355/dbbs.084-200511080100-231 · Cited by 170
Combinatorial optimization and vehicle fleet planning: Perspectives and prospects
Magnanti, T. L. (1981) · Networks · doi:10.1002/net.3230110209 · Cited by 166
Submodular Optimization with Routing Constraints
Zhang, H., & Vorobeychik, Y. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.10066 · Cited by 164
Smith, S. L., & Imeson, F. (2017) · Computers & Operations Research · doi:10.1016/j.cor.2017.05.010 · Cited by 163
On the Dubins Traveling Salesman Problem
Le Ny, J., Feron, E., & Frazzoli, E. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2166311 · Cited by 161
A Bee Colony Optimization Algorithm for Traveling Salesman Problem
Wong, L., Low, M. Y. H., & Chong, C. S. (2008) · Asia International Conference on Modelling & Simulation (AMS) · doi:10.1109/ams.2008.27 · Cited by 161
Reinforcement Learning With Multiple Relational Attention for Solving Vehicle Routing Problems
Xu, Y., Fang, M., Chen, L., Xu, G., Du, Y., & Zhang, C. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2021.3089179 · Cited by 160
A climbing autonomous robot for inspection applications in 3D complex environments
Balaguer, C., Giménez, A., Pastor, J. M., Padrón, V. M., & Abderrahim, M. (2000) · Robotica · doi:10.1017/s0263574799002258 · Cited by 159
TSP- Infrastructure for the Traveling Salesperson Problem
Hahsler, M., & Hornik, K. (2007) · Journal of Statistical Software · doi:10.18637/jss.v023.i02 · Cited by 158
A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs
Hu, Y., Yao, Y., & Lee, W. S. (2020) · Knowledge-Based Systems · doi:10.1016/j.knosys.2020.106244 · Cited by 157
Large Language Models as Optimizers
Yang, C., Wang, X., Lu, Y., Liu, H., Le, Q. V., Zhou, D., & Chen, X. (2023) · arXiv · doi:10.48550/arxiv.2309.03409 · Cited by 151
Local ratio: A unified framework for approximation algorithms. In Memoriam: Shimon Even 1935-2004
Bar-Yehuda, R., Bendel, K., Freund, A., & Rawitz, D. (2004) · ACM Computing Surveys · doi:10.1145/1041680.1041683 · Cited by 142
Multi-Depot Vehicle Routing Problem: A One-Stage Approach
Lim, A. E. B., & Wang, F. (2005) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2005.853472 · Cited by 141
Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
Lee, D. T., & Wong, C. K. (1980) · SIAM Journal on Computing · doi:10.1137/0209017 · Cited by 141
Approximating Capacitated Routing and Delivery Problems
Chalasani, P., & Motwani, R. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539795295468 · Cited by 139
Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time
Drori, I., Kharkar, A., Sickinger, W. R., Kates, B., Ma, Q., Ge, S., Dolev, E., Dietrich, B. L., Williamson, D. P., & Udell, M. R. (2020) · International Conference on Machine Learning and Applications · doi:10.1109/icmla51294.2020.00013 · Cited by 137
Fast hierarchical clustering and other applications of dynamic closest pairs
Eppstein, D. (2000) · ACM Journal of Experimental Algorithmics · doi:10.1145/351827.351829 · Cited by 137
Gu, J., & Huang, X. (1994) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/21.293486 · Cited by 137
Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic DesignPreprint
Zheng, Z., Xie, Z., Wang, Z., & Hooi, B. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2501.08603 · Cited by 136
The single vehicle routing problem with deliveries and selective pickups
Gribkovskaia, I. V., Laporte, G., & Shyshou, A. (2007) · Computers & Operations Research · doi:10.1016/j.cor.2007.01.007 · Cited by 133
Heuristic methods and applications: A categorized survey
Zanakis, S. H., Evans, J. R., & Vazacopoulos, A. (1989) · European Journal of Operational Research · doi:10.1016/0377-2217(89)90412-8 · Cited by 131
Solomon, M. M. (1986) · Networks · doi:10.1002/net.3230160205 · Cited by 130
An Exact Algorithm for Heterogeneous Drone-Truck Routing Problem
Kang, M., & Lee, C. (2021) · Transportation Science · doi:10.1287/trsc.2021.1055 · Cited by 128
Khan, M. K. U., Pandurangan, G., & Kumar, V. S. A. (2008) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2008.57 · Cited by 127
Honey bees mating optimization algorithm for the Euclidean traveling salesman problem
Marinakis, Y., Marinaki, M., & Dounias, G. D. (2010) · Information Sciences · doi:10.1016/j.ins.2010.06.032 · Cited by 123
General solutions to the single vehicle routing problem with pickups and deliveries
Gribkovskaia, I. V., Halskau, Ø., Laporte, G., & Vlček, M. (2006) · European Journal of Operational Research · doi:10.1016/j.ejor.2006.05.009 · Cited by 123
Iterated local search heuristics for the Vehicle Routing Problem with Cross-Docking
Morais, V. W. C., Mateus, G. R., & Noronha, T. F. (2014) · Expert Systems with Applications · doi:10.1016/j.eswa.2014.06.010 · Cited by 122
Optimal UAV Route Planning for Coverage Search of Stationary Target in River
Yao, P., Xie, Z., & Ren, P. (2017) · IEEE Transactions on Control Systems Technology · doi:10.1109/tcst.2017.2781655 · Cited by 121
Further results on the probabilistic traveling salesman problem
Bertsimas, D., & Howell, L. H. (1993) · European Journal of Operational Research · doi:10.1016/0377-2217(93)90145-d · Cited by 120
On a Greedy Heuristic for Complete Matching
Reingold, E. M., & Tarjan, R. E. (1981) · SIAM Journal on Computing · doi:10.1137/0210050 · Cited by 117
Vehicle routing with pick-up and delivery: tour-partitioning heuristics
Mosheiov, G. (1998) · Computers & Industrial Engineering · doi:10.1016/s0360-8352(97)00275-1 · Cited by 114
A modified ant colony system for solving the travelling salesman problem with time windows
Cheng, C.-B., & Mao, C.-P. (2007) · Mathematical and Computer Modelling · doi:10.1016/j.mcm.2006.11.035 · Cited by 110
On the nearest neighbor rule for the traveling salesman problem
Hurkens, C. A. J., & Woeginger, G. J. (2003) · Operations Research Letters · doi:10.1016/s0167-6377(03)00093-2 · Cited by 109
On the Invariance of Ant Colony Optimization
Birattari, M., Pellegrini, P., & Dorigo, M. (2007) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2007.892762 · Cited by 107
Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics
Lin, S.-W., & Ying, K. (2015) · Omega · doi:10.1016/j.omega.2015.12.002 · Cited by 102
A Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem
Xing, Z., & Tu, S. (2020) · IEEE Access · doi:10.1109/access.2020.3000236 · Cited by 100
A fast distributed approximation algorithm for minimum spanning trees
Khan, M., & Pandurangan, G. (2007) · Distributed Computing · doi:10.1007/s00446-007-0047-8 · Cited by 100
Sindhuchao, S., Romeijn, H. E., Akçalı, E., & Boondiskulchok, R. (2005) · Journal of Global Optimization · doi:10.1007/s10898-004-5908-0 · Cited by 99
Reoptimizing the traveling salesman problem
Archetti, C., Bertazzi, L., & Speranza, M. G. (2003) · Networks · doi:10.1002/net.10091 · Cited by 98
Heuristics for Vehicle Routing Problem: A Survey and Recent AdvancesPreprint
Liu, F., Lu, C., Gui, L., Zhang, Q., Tong, X., & Yuan, M. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2303.04147 · Cited by 98
Implementation of an Ant Colony Optimization technique for job shop scheduling problem
Zhang, J., Hu, X.-M., Tan, X., Zhong, J. H., & Huang, Q. (2006) · Transactions of the Institute of Measurement and Control · doi:10.1191/0142331206tm165oa · Cited by 97
On the Nearest Neighbor Algorithms for the Traveling Salesman Problem
Kizilates-Evin, G., & Nuriyeva, F. (2013) · Advances in intelligent systems and computing · doi:10.1007/978-3-319-00951-3_11 · Cited by 97
On Subset Selection with General Cost Constraints
Qian, C., Shi, J.-C., Yu, Y., & Tang, K. (2017) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2017/364 · Cited by 95
Multi-period inventory routing problem under carbon emission regulations
Cheng, C., Qi, M., Wang, X., & Zhang, Y. (2016) · International Journal of Production Economics · doi:10.1016/j.ijpe.2016.09.001 · Cited by 93
Insertion techniques for the heuristic solution of the job shop problem
Werner, F. M., & Winkler, A. (1995) · Discrete Applied Mathematics · doi:10.1016/0166-218x(93)e0127-k · Cited by 93
Constructing competitive tours from local information
Kalyanasundaram, B., & Pruhs, K. R. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90155-4 · Cited by 93
The Traveling Salesman Problem and its Variations
Monnot, J., & Toulouse, S. (2013) · Wiley eBooks · doi:10.1002/9781118600207.ch7 · Cited by 92
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.