The TSP phase transition
From MaRDI portal
Publication:1391912
DOI10.1016/S0004-3702(96)00030-6zbMath0907.68177OpenAlexW2096041053MaRDI QIDQ1391912
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
complexityNP-complete problemstraveling salesman problemfinite-size scalingeasy and hard instancessearch phase transitions
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
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