On the classification of NP-complete problems in terms of their correlation coefficient
From MaRDI portal
Publication:1962048
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; zbMATH DE number 175833
- scientific article; zbMATH DE number 4003531
- scientific article; zbMATH DE number 17527
- scientific article; zbMATH DE number 3874957
- scientific article; zbMATH DE number 4001486
- Correlation decay and tractability of CSPs
- The relative complexity of NP search problems
Cites work
- scientific article; zbMATH DE number 3916170 (Why is no real title available?)
- scientific article; zbMATH DE number 41891 (Why is no real title available?)
- scientific article; zbMATH DE number 177832 (Why is no real title available?)
- scientific article; zbMATH DE number 1062113 (Why is no real title available?)
- scientific article; zbMATH DE number 1488095 (Why is no real title available?)
- Algodesk: An experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem
- An improved annealing scheme for the QAP
- Autocorrelation coefficient for the graph bipartitioning problem
- Convergence of an annealing algorithm
- Cooling Schedules for Optimal Annealing
- Correlated and uncorrelated fitness landscapes and how to tell the difference
- Landscapes and their correlation functions
- Local search and the local structure of NP-complete problems
- On the depth of combinatorial optimization problems
- On the landscape ruggedness of the quadratic assignment problem
- On the quality of local search for the quadratic assignment problem
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
- Paths, Trees, and Flowers
- The depth and width of local minima in discrete solution spaces
- Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
- Traveling salesman problem and local search
Cited in
(17)- The linear ordering problem: instances, search space analysis and algorithms
- Autocorrelation measures for the quadratic assignment problem
- An analysis of neighborhood functions on generic solution spaces
- On the landscape ruggedness of the quadratic assignment problem
- 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
- Random walk's correlation function for multi-objective NK landscapes and quadratic assignment problem
- 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
- Rugged and elementary landscapes
- Using the method of conditional expectations to supply an improved starting point for CCLS
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)
