On the classification of NP-complete problems in terms of their correlation coefficient
DOI10.1016/S0166-218X(99)00138-9zbMATH Open0987.90092MaRDI QIDQ1962048FDOQ1962048
Publication date: 3 July 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Recommendations
- Correlation of NP-sets and co-NP-sets with respect to a random oracle
- The Complexity of Problems in P Given Correlated Instances
- Co-NP-completeness of some matrix classification problems
- scientific article
- Publication:4728249
- scientific article; zbMATH DE number 17527
- scientific article; zbMATH DE number 3874957
- Publication:4727432
- Correlation decay and tractability of CSPs
- The relative complexity of NP search problems
local searchmeta-heuristicsproblemsautocorrelation coefficientclassification of combinatorial optimization
Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms (68W40) Search theory (90B40) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Paths, Trees, and Flowers
- Convergence of an annealing algorithm
- Cooling Schedules for Optimal Annealing
- Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
- Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
- Title not available (Why is that?)
- Landscapes and their correlation functions
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- Algodesk: An experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem
- Title not available (Why is that?)
- An improved annealing scheme for the QAP
- Correlated and uncorrelated fitness landscapes and how to tell the difference
- Local search and the local structure of NP-complete problems
- On the landscape ruggedness of the quadratic assignment problem
- Autocorrelation coefficient for the graph bipartitioning problem
- On the quality of local search for the quadratic assignment problem
- Title not available (Why is that?)
- Traveling salesman problem and local search
- The depth and width of local minima in discrete solution spaces
- On the depth of combinatorial optimization problems
- Title not available (Why is that?)
Cited In (16)
- The linear ordering problem: instances, search space analysis and algorithms
- Rugged and Elementary Landscapes
- Autocorrelation measures for the quadratic assignment problem
- On the landscape ruggedness of the quadratic assignment problem
- An analysis of neighborhood functions on generic solution spaces
- A survey for the quadratic assignment problem
- The Complexity of Problems in P Given Correlated Instances
- The Normalized Autocorrelation Length of Random Max $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
- Probabilistic characterization of random Max \(r\)-Sat
- Exploring the role of graph spectra in graph coloring algorithm performance
- Measuring instance difficulty for combinatorial optimization problems
- Construction of the developing connecting tree
- A multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem
- Evaluation of reliability bounds by set covering models.
- A useful transform of standard input data for a classical NP-complete problem
- Using the method of conditional expectations to supply an improved starting point for CCLS
Uses Software
This page was built for publication: On the classification of NP-complete problems in terms of their correlation coefficient
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962048)
