On the classification of NP-complete problems in terms of their correlation coefficient
From MaRDI portal
Publication:1962048
DOI10.1016/S0166-218X(99)00138-9zbMath0987.90092MaRDI QIDQ1962048
Eric Angel, Vassilios Zissimopoulos
Publication date: 3 July 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
local searchmeta-heuristicsproblemsautocorrelation coefficientclassification of combinatorial optimization
Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Search theory (90B40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
Rugged and Elementary Landscapes ⋮ A survey for the quadratic assignment problem ⋮ Exploring the role of graph spectra in graph coloring algorithm performance ⋮ Construction of the developing connecting tree ⋮ Autocorrelation measures for the quadratic assignment problem ⋮ Evaluation of reliability bounds by set covering models. ⋮ An analysis of neighborhood functions on generic solution spaces ⋮ Measuring instance difficulty for combinatorial optimization problems ⋮ A multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem ⋮ The linear ordering problem: instances, search space analysis and algorithms ⋮ Probabilistic characterization of random Max \(r\)-Sat ⋮ The Normalized Autocorrelation Length of Random Max $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$ ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improved annealing scheme for the QAP
- Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
- Correlated and uncorrelated fitness landscapes and how to tell the difference
- Autocorrelation coefficient for the graph bipartitioning problem
- Algodesk: An experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem
- Traveling salesman problem and local search
- Local search and the local structure of NP-complete problems
- The depth and width of local minima in discrete solution spaces
- Landscapes and their correlation functions
- On the quality of local search for the quadratic assignment problem
- On the depth of combinatorial optimization problems
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- Convergence of an annealing algorithm
- Cooling Schedules for Optimal Annealing
- Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
- Paths, Trees, and Flowers
- On the landscape ruggedness of the quadratic assignment problem
