A study of complexity transitions on the asymmetric traveling salesman problem

DOI10.1016/0004-3702(95)00054-2OpenAlexW1983101156MaRDI QIDQ2674187

Weixiong Zhang, Richard E. Korf

Publication date: 22 September 2022

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(95)00054-2

zbMATH Keywords

complexitycombinatorial optimizationphase transitionstraveling salesman problemproblem solvingsearch

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (10)

Discrete heat transfer search for solving travelling salesman problem ⋮ Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems ⋮ Experimental complexity analysis of continuous constraint satisfaction problems. ⋮ On the performance of MaxSAT and MinSAT solvers on 2SAT-MaxOnes ⋮ Measuring instance difficulty for combinatorial optimization problems ⋮ Quantum optimization ⋮ A complete anytime algorithm for number partitioning ⋮ SAT distributions with planted assignments and phase transitions between decision and optimization problems ⋮ SAT Distributions with Phase Transitions between Decision and Optimization Problems ⋮ Unifying single-agent and two-player search

Cites Work

• Exploiting the deep structure of constraint problems
• Searching for an optimal path in a tree with random costs
• Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems
• Random Trees and the Analysis of Branch and Bound Procedures
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Technical Note—On the Expected Performance of Branch-and-Bound Algorithms
• Branch-and-Bound Methods: A Survey
• An Algorithm for the Traveling Salesman Problem
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• Performance of linear-space search algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A study of complexity transitions on the asymmetric traveling salesman problem