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 301–400 of 1,000
Two - Echelon Vehicle Routing Problem with Recharge Stations
Agárdi, A., Kovács, L., & Bányai, T. (2019) · Transport and Telecommunication Journal · doi:10.2478/ttj-2019-0025 · Cited by 20
Dynamic Shortest Paths Methods for the Time-Dependent TSP
Hansknecht, C., Joormann, I., & Stiller, S. (2021) · Algorithms · doi:10.3390/a14010021 · Cited by 20
An agent-based modeling framework for the multi-UAV rendezvous recharging problem
Chour, K., Reddinger, J.-P., Dotterweich, J. M., Childers, M., Humann, J. D., Rathinam, S., & Darbha, S. (2023) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2023.104442 · Cited by 20
Cost of sequential connection for points in space
Steele, J. M. (1989) · Operations Research Letters · doi:10.1016/0167-6377(89)90039-4 · Cited by 20
Ant Colony optimization technique to Solve the min-max multi depot vehicle routing problem
Narasimha, K. S. V., Kivelevitch, E. H., & Kumar, M. (2012) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2012.6315583 · Cited by 20
Solving the asymmetric traveling salesman problem with periodic constraints
Paletta, G., & Triki, C. (2004) · Networks · doi:10.1002/net.20011 · Cited by 20
Hertz, A., & Mittaz, M. (2000) · Springer eBooks · doi:10.1007/978-1-4615-4495-1_9 · Cited by 20
Vehicle Routing and the Supply Chain
Anily, S., & Bramel, J. (1999) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4615-4949-9_6 · Cited by 20
An empirical study of a new metaheuristic for the traveling salesman problem
Tsubakitani, S., & Evans, J. R. (1998) · European Journal of Operational Research · doi:10.1016/s0377-2217(96)00334-7 · Cited by 20
Real-time control strategies for multiple-load AGVs
Tanchoco, J. M. A., & Co, C. G. (1994) · Springer eBooks · doi:10.1007/978-1-4615-2498-4_11 · Cited by 20
Zhang, Y., Zhang, R., & Li, H. (2023) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2023.3260071 · Cited by 19
Computing a k-Route over Uncertain Geographical Data
Safra, E., Kanza, Y., Dolev, N., Sagiv, Y., & Doytsher, Y. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73540-3_16 · Cited by 19
Online graph exploration on a restricted graph class: Optimal solutions for tadpole graphs
Brandt, S., Foerster, K.-T., Maurer, J., & Wattenhofer, R. P. (2020) · Theoretical Computer Science · doi:10.1016/j.tcs.2020.06.007 · Cited by 19
Gencer, C., Top, İ., & Aydoğan, E. K. (2006) · Applied Mathematics and Computation · doi:10.1016/j.amc.2006.02.043 · Cited by 19
Applying Graph Theory to Problems in Air Traffic Management
Farrahi, A. H., Goldberg, A. T., Bagasol, L., & Jung, J. (2017) · AIAA Aviation Technology, Integration, and Operations Conference (ATIO) · doi:10.2514/6.2017-3775 · Cited by 19
The traveling salesman puts-on a hard hat – Tower crane scheduling in construction projects
Tarhini, H., Maddah, B., & Hamzeh, F. (2020) · European Journal of Operational Research · doi:10.1016/j.ejor.2020.10.029 · Cited by 19
Seyffarth, T., & Kühnel, S. (2020) · Journal of Decision System · doi:10.1080/12460125.2020.1861920 · Cited by 20
A location-routing problem in glass recycling
Rahim, F., & Sepil, C. (2014) · Annals of Operations Research · doi:10.1007/s10479-014-1621-7 · Cited by 19
The Traveling Salesman Problem
Körte, B., & Vygen, J. (2018) · Algorithms and combinatorics · doi:10.1007/978-3-662-56039-6_21 · Cited by 19
Abstract Architecture for Task-oriented Multi-agent Problem Solving
Vokřínek, J., Komenda, A., & Pěchouček, M. (2010) · IEEE Transactions on Systems Man and Cybernetics Part C (Applications and Reviews) · doi:10.1109/tsmcc.2010.2073465 · Cited by 19
Maximal Weighted Coverage Deployment of UAV-Enabled Rechargeable Visual Sensor Networks
Zhu, X., & Zhou, M. (2023) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2023.3276813 · Cited by 18
Klamler, C., & Pferschy, U. (2007) · Social Choice and Welfare · doi:10.1007/s00355-006-0214-z · Cited by 18
The Traveling Salesman Problem
(2007) · Springer eBooks · doi:10.1007/978-3-540-71844-4_21 · Cited by 18
Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
Nayak, A., & Rathinam, S. (2023) · Sensors · doi:10.3390/s23146432 · Cited by 18
Hybrid Heuristic Approaches for Scheduling in Reconfigurable Manufacturing Systems
de Vega, R. G. (2008) · Studies in computational intelligence · doi:10.1007/978-3-540-78985-7_9 · Cited by 18
Constructing competitive tours from local information
Kalyanasundaram, B., & Pruhs, K. R. (1993) · Lecture notes in computer science · doi:10.1007/3-540-56939-1_65 · Cited by 18
Distance-Based Index Structures for Fast Similarity Search
Rachkovskij, D. A. (2017) · Cybernetics and Systems Analysis · doi:10.1007/s10559-017-9966-y · Cited by 18
Geiß, C., Thoma, M., & Taubenböck, H. (2018) · IEEE Geoscience and Remote Sensing Letters · doi:10.1109/lgrs.2018.2813436 · Cited by 18
Hybrid optimizer for the travelling salesman problem
Sahana, S. K. (2019) · Evolutionary Intelligence · doi:10.1007/s12065-019-00208-7 · Cited by 18
A Farthest First Traversal based Sampling Algorithm for k-clustering
Trang, L. H., Hoang, N. L., & Dang, T. K. (2020) · International Conference on Ubiquitous Information Management and Communication (IMCOM) · doi:10.1109/imcom48794.2020.9001738 · Cited by 18
Hashimoto, H., Yagiura, M., Imahori, S., & Ibaraki, T. (2013) · Annals of Operations Research · doi:10.1007/s10479-012-1264-5 · Cited by 18
A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem
Xu, Z., & Rodrigues, B. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13731-0_13 · Cited by 18
ITERATED TABU SEARCH FOR THE TRAVELING SALESMAN PROBLEM: NEW RESULTS
Misevičius, A., Smolinskas, J., & Tomkevičius, A. (2005) · Information Technology And Control · doi:10.5755/j01.itc.34.4.12028 · Cited by 18
Multi-Agent Pickup And Delivery Planning With Transfers
Coltin, B. (2018) · KiltHub Repository · doi:10.1184/r1/6720740 · Cited by 18
An Air Force Crew Allocation and Scheduling Problem
Sherali, H. D., & Rios, M. (1984) · Journal of the Operational Research Society · doi:10.1057/jors.1984.16 · Cited by 17
Fitness Landscape Analysis and Edge Weighting-Based Optimization of Vehicle Routing Problems
Kovács, L., Agárdi, A., & Bányai, T. (2020) · Processes · doi:10.3390/pr8111363 · Cited by 17
Robustification of Online Graph Exploration Methods
Eberle, F. C., Lindermayr, A., Megow, N., Nölke, L., & Schlöter, J. (2022) · AAAI Publications (The Association for the Advancement of Artificial Intelligence (AAAI)) · doi:10.1609/aaai.v36i9.21208 · Cited by 17
Informable Multi-Objective and Multi-Directional RRT* System for Robot Path Planning
Huang, J.-K., Tan, Y., Lee, D., Desaraju, V. R., & Grizzle, J. W. (2023) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra48891.2023.10160838 · Cited by 17
A new and efficient ant‐based heuristic method for solving the traveling salesman problem
Tsai, C.-F., Tsai, C., & Tseng, C. (2003) · Expert Systems · doi:10.1111/1468-0394.00242 · Cited by 17
AN ASSIGNMENT-BASED LOCAL SEARCH METHOD FOR SOLVING VEHICLE ROUTING PROBLEMS
Zeng, L., Ong, H. L., & Ng, K. M. (2005) · Asia Pacific Journal of Operational Research · doi:10.1142/s0217595905000479 · Cited by 17
Special cases of travelling salesman problems and heuristics
Rainer, E. B. (1990) · Acta Mathematicae Applicatae Sinica English Series · doi:10.1007/bf02019153 · Cited by 17
Technical Proceedings of the Amazon Last Mile Routing Research Challenge
Winkenbach, M., Parks, S. N., & Noszek, J. (2021) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 17
Learning to Insert for Constructive Neural Vehicle Routing Solver
Luo, F., Lin, X., Zhong, M., Liu, F., Wang, Z., Sun, J., & Zhang, Q. (2025) · neural information processing systems · doi:10.52202/085713-2918 · Cited by 16
Ultrafast Electronic Coupling Estimators: Neural Networks versus Physics-Based Approaches
Hafizi, R., Elsner, J., & Blumberger, J. (2023) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.3c00184 · Cited by 16
Energy-efficient clustering and path planning for UAV-assisted D2D cellular networks
Gouda, K. C., & Thakur, R. (2025) · Ad Hoc Networks · doi:10.1016/j.adhoc.2025.103757 · Cited by 16
Rahman, M. A., & Parvez, H. (2021) · OALib · doi:10.4236/oalib.1107520 · Cited by 16
A Hybrid BSO-ACO for Dynamic Vehicle Routing Problem on Real-World Road Networks
Liu, M., Song, Q., Zhao, Q. G., Li, L., Yang, Z., & Zhang, Y. (2022) · IEEE Access · doi:10.1109/access.2022.3221191 · Cited by 16
Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
Bhore, S., Filtser, A., & Tóth, C. D. (2024) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977912.162 · Cited by 16
Kong, X., Schunn, C. D., & Wallstrom, G. L. (2010) · Cognitive Science · doi:10.1111/j.1551-6709.2009.01075.x · Cited by 16
Online graph exploration on trees, unicyclic graphs and cactus graphs
Fritsch, R. (2021) · Information Processing Letters · doi:10.1016/j.ipl.2021.106096 · Cited by 16
Reactive Mission Planning for UAV based crane rail inspection in an automated Container Terminal
Bobbe, M., Khedar, Y., Backhaus, J., Gerke, M., Ghassoun, Y., & Plöger, F. (2020) · International Conference on Unmanned Aircraft Systems (ICUAS) · doi:10.1109/icuas48674.2020.9213854 · Cited by 16
Huấn, H. X., Trung, N. L., Đông, Đ. Đ., & Huynh, H.-T. (2013) · REV Journal on Electronics and Communications · doi:10.21553/rev-jec.44 · Cited by 16
Automated and Cycle Time Optimized Path Planning for Robot-Based Inspection Systems
Ulrich, M., Lux, G., Jürgensen, L., & Reinhart, G. (2016) · Procedia CIRP · doi:10.1016/j.procir.2016.02.021 · Cited by 16
Algorithms for solving the location : routing problem
Srivastava, R. V. (1986) · OhioLink ETD Center (Ohio Library and Information Network) · Cited by 16
Consensus-based auctions for decentralized task assignment
Brunet, L. (2008) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 16
On solving close enough orienteering problems with overlapped neighborhoods
Qian, Q., Wang, Y., & Boyle, D. (2024) · European Journal of Operational Research · doi:10.1016/j.ejor.2024.05.032 · Cited by 15
Distributed MPC of constrained linear systems with time-varying terminal sets
Wang, Z., & Ong, C. (2015) · Systems & Control Letters · doi:10.1016/j.sysconle.2015.11.005 · Cited by 15
Microaggregation heuristic applied to statistical disclosure control
Fadel, A. C., Ochi, L. S., Brito, J. A. D. M., & Semaan, G. S. (2020) · Information Sciences · doi:10.1016/j.ins.2020.09.069 · Cited by 15
Transgenetic Algorithm: A New Endosymbiotic Approach for Evolutionary Algorithms
Goldbarg, E. F. G., & Goldbarg, M. C. (2009) · Studies in computational intelligence · doi:10.1007/978-3-642-01085-9_14 · Cited by 15
Construction and improvement heuristics applied to the capacitated vehicle routing problem
Tavares, L. G., Lopes, H. S., & Lima, C. R. E. (2009) · World Congress on Nature and Biologically Inspired Computing (NaBIC) · doi:10.1109/nabic.2009.5393467 · Cited by 15
Not all insertion methods yield constant approximate tours in the Euclidean plane
Bafna, V., Kalyanasundaram, B., & Pruhs, K. R. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90257-7 · Cited by 15
Scheduling of page fetches in join operations using B/sub c/-trees
Goyal, P., Li, H. F., Regener, E., & Sadri, F. (2003) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.1988.105473 · Cited by 15
Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model
Liu, F., Tong, X., Yuan, M., Lin, X., Luo, F., Wang, Z., Lu, Z., & Zhang, Q. (2024) · arXiv · doi:10.48550/arxiv.2401.02051 · Cited by 14
Improvement of the Nearest Neighbor Heuristic Search Algorithm for Traveling Salesman Problem
Rahman, M. Z., Sheikh, S. R., Islam, A., & Rahman, M. A. (2024) · Journal of Engineering Advancements · doi:10.38032/jea.2024.01.004 · Cited by 14
Gyromorphs: A New Class of Functional Disordered Materials
Casiulis, M., Shih, A., & Martiniani, S. (2025) · Physical Review Letters · doi:10.1103/gqrx-7mn2 · Cited by 14
Task Sequencing for Remote Laser Welding in the Automotive Industry
Kovács, A. (2013) · Proceedings of the International Conference on Automated Planning and Scheduling · doi:10.1609/icaps.v23i1.13581 · Cited by 14
Lister, A. J., Lister, T. W., & Weber, T. (2019) · Forests · doi:10.3390/f10100896 · Cited by 14
Auction algorithm sensitivity for multi-robot task allocation
Clinch, K., Wood, T. A., & Manzie, C. G. (2023) · Automatica · doi:10.1016/j.automatica.2023.111239 · Cited by 14
Zhang, B., & Ravindran, B. (2009) · IEEE Symposium on Reliable Distributed Systems (SRDS) · doi:10.1109/srds.2009.33 · Cited by 14
Freeman, I. C., Haigler, A. J., Schmeelk, S., Ellrodt, L. R., & Fields, T. L. (2018) · International Conference on Machine Learning and Applications · doi:10.1109/icmla.2018.00217 · Cited by 14
Converting MST to TSP Path by Branch Elimination
Fränti, P., Nenonen, T., & Yuan, M. (2020) · Applied Sciences · doi:10.3390/app11010177 · Cited by 14
A Generic Bee Colony Optimization Framework for Combinatorial Optimization Problems
Wong, L., Low, M. Y. H., & Chong, C. S. (2010) · Asia International Conference on Mathematical/Analytical Modelling and Computer Simulation · doi:10.1109/ams.2010.41 · Cited by 14
MDPF: Minimum Distance Packet Forwarding for Search Applications in Mobile Ad Hoc Networks
Artail, H. A., & Mershad, K. (2009) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2009.56 · Cited by 14
An effective ant-based algorithm for the degree-constrained minimum spanning tree problem
Doan, M. N. U. (2007) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2007.4424510 · Cited by 14
Alto: A computer system for the design of vehicle routing algorithms
Potvin, J., Lapalme, G., & Rousseau, J. M. (1989) · Computers & Operations Research · doi:10.1016/0305-0548(89)90033-6 · Cited by 14
On the complexity of designing optimal partial-match retrieval systems
Moran, S. (1983) · ACM Transactions on Database Systems · doi:10.1145/319996.320004 · Cited by 14
Analysis of the performance of dynamic multicast routing algorithms
Cho, J., & Breen, J. (1999) · Computer Communications · doi:10.1016/s0140-3664(99)00009-2 · Cited by 14
A location-or-routing problem with partial and decaying coverage
Haghi, M., Arslan, O., & Laporte, G. (2022) · Computers & Operations Research · doi:10.1016/j.cor.2022.106041 · Cited by 13
An edge-aware graph autoencoder trained on scale-imbalanced data for traveling salesman problems
Liu, S., Yan, X., & Jin, Y. (2024) · Knowledge-Based Systems · doi:10.1016/j.knosys.2024.111559 · Cited by 13
A Framework for Automated Dissection Along Tissue Boundary
Oh, K.-H., Borgioli, L., Žefran, M., Chen, L., & Giulianotti, P. C. (2024) · IEEE/RAS-EMBS International Conference on Biomedical Robotics and Biomechatronics (BioRob) · doi:10.1109/biorob60516.2024.10719948 · Cited by 13
Variable-Speed Traveling Salesman Problem for Vehicles with Curvature Constrained Trajectories
Kučerová, K., Váňa, P., & Faigl, J. (2021) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros51168.2021.9636762 · Cited by 13
Ammi, M., & Chıkhı, S. (2015) · Journal of Computing and Information Technology · doi:10.2498/cit.1002465 · Cited by 13
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
Künnemann, M., & Manthey, B. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-47672-7_70 · Cited by 13
Handling uncertainties in vehicle routing problems through data preprocessing
Chardy, M., & Klopfenstein, O. (2012) · Transportation Research Part E Logistics and Transportation Review · doi:10.1016/j.tre.2011.12.001 · Cited by 13
Levin, A., & Yovel, U. (2012) · Journal of Combinatorial Optimization · doi:10.1007/s10878-012-9580-x · Cited by 13
Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems
Bringmann, K., Engels, C., Manthey, B., & Rao, B. V. R. (2014) · Algorithmica · doi:10.1007/s00453-014-9901-9 · Cited by 13
Comparative Study of Meta-Heuristic Approaches for Solving Traveling Salesman Problems
Arram, A. W., Ayob, M. B., & Zakree, M. (2014) · Asian Journal of Applied Sciences · doi:10.3923/ajaps.2014.662.670 · Cited by 13
Modeling with Copulas and Vines in Estimation of Distribution AlgorithmsPreprint
Soto, M., González-Fernández, Y., & Ochoa, A. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1210.5500 · Cited by 13
Heuristic and Metaheuristic Algorithms for the Traveling Salesman Problem
Marinakis, Y. (2008) · Springer eBooks · doi:10.1007/978-0-387-74759-0_262 · Cited by 13
Chapin, B. (2001) · University of North Texas Digital Library (University of North Texas) · doi:10.12794/metadc2909 · Cited by 13
A Carnivorous Plant Algorithm With Heuristic Decoding Method for Traveling Salesman Problem
Wang, J., Zhang, P., Zhang, H., Song, H., Bei, J., Sun, W., & Sun, X. (2022) · IEEE Access · doi:10.1109/access.2022.3205756 · Cited by 12
A Computation Investigation of the Impact of Convex Hull subtour on the Nearest Neighbour Heuristic
Asani, E. O., Okeyinka, A. E., & Adebiyi, A. A. (2023) · International Conference on Science, Engineering and Business for Sustainable Development Goals (SEB-SDG) · doi:10.1109/seb-sdg57117.2023.10124469 · Cited by 12
A Novel Insertion Solution for the Travelling Salesman Problem
Asani, E. O., Okeyinka, A. E., Ajagbe, S. A., Adebiyi, A. A., Ogundokun, R. O., Adekunle, T. S., Mudali, P., & Adigun, M. O. (2024) · Computers, materials & continua/Computers, materials & continua (Print) · doi:10.32604/cmc.2024.047898 · Cited by 12
The emergence of enhanced intelligence in a brain-inspired cognitive architecture
Schneider, H. (2024) · Frontiers in Computational Neuroscience · doi:10.3389/fncom.2024.1367712 · Cited by 12
Scaling laws of dynamic high-capacity ride-sharing
Chen, W., Yang, L., Chen, X. M., & Ke, J. (2025) · Transportation Research Part C Emerging Technologies · doi:10.1016/j.trc.2025.105064 · Cited by 12
Planning for hazardous campus waste collection
Liu, K.-H., Shih, S.-Y., & Kao, J. (2011) · Journal of Hazardous Materials · doi:10.1016/j.jhazmat.2011.02.046 · Cited by 12
An Improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks
Xiong, N. N., Wu, W., & Wu, C. (2017) · Sustainability · doi:10.3390/su9060985 · Cited by 12
Soliman, E., Mogefors, D., & Bergmann, J. (2020) · Health and Technology · doi:10.1007/s12553-020-00450-5 · Cited by 12
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0010 · Cited by 12
Subset Selection for Hybrid Task Scheduling with General Cost Constraints
Sun, Y., Lin, C., Ren, J., Wang, P., Wang, L., Wu, G., & Zhang, Q. (2022) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom48880.2022.9796947 · Cited by 12
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.