The TSP phase transition

DOI10.1016/S0004-3702(96)00030-6zbMath0907.68177OpenAlexW2096041053MaRDI QIDQ1391912

Ian Philip Gent, Toby Walsh

Publication date: 23 July 1998

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

Full work available at URL: https://doi.org/10.1016/s0004-3702(96)00030-6

zbMATH Keywords

complexityNP-complete problemstraveling salesman problemfinite-size scalingeasy and hard instancessearch phase transitions

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (19)

Generic properties of a computational task predict human effort and performance ⋮ Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study ⋮ A new class of hard problem instances for the 0-1 knapsack problem ⋮ PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP ⋮ The TSP phase transition ⋮ Exploring the role of graph spectra in graph coloring algorithm performance ⋮ Discovering the suitability of optimisation algorithms by learning from evolved instances ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO ⋮ Is computational complexity a barrier to manipulation? ⋮ Phase transitions of contingent planning problem ⋮ Phase Transition for Maximum Not-All-Equal Satisfiability ⋮ Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension ⋮ Measuring instance difficulty for combinatorial optimization problems ⋮ The Travelling Salesman Problem for finite-sized cities ⋮ PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS ⋮ Quantum branch-and-bound algorithm and its application to the travelling salesman problem ⋮ SAT distributions with planted assignments and phase transitions between decision and optimization problems ⋮ SAT Distributions with Phase Transitions between Decision and Optimization Problems

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• The hardest constraint problems: A double phase transition
• Easy problems are sometimes hard
• The TSP phase transition
• Experimental results on the crossover point in random 3-SAT
• Critical behavior in the computational cost of satisfiability testing
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
• TSPLIB—A Traveling Salesman Problem Library

This page was built for publication: The TSP phase transition