What makes an optimization problem hard?.

DOI10.1002/CPLX.6130010511MaRDI QIDQ960453zbMATH OpenOpenAlexFDO

Authors William G. Macready, David Wolpert

Publication date 21 December 2008

Published in Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/cplx.6130010511

zbMATH Keywords

combinatorial optimizationhardnessoptimization algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Measuring instance difficulty for combinatorial optimization problems
• The complexity of optimization problems
• A complex-networks view of hard combinatorial search spaces
• On the typical case complexity of graph optimization
• scientific article; zbMATH DE number 67483

Cited in

(11)

• Theory versus practice in annealing-based quantum computing
• Connections in Networks: Hardness of Feasibility Versus Optimality
• scientific article; zbMATH DE number 4001485 (Why is no real title available?)
• What Is Important About the No Free Lunch Theorems?
• Exploring the role of graph spectra in graph coloring algorithm performance
• Discovering the suitability of optimisation algorithms by learning from evolved instances
• Measuring instance difficulty for combinatorial optimization problems
• Generating new test instances by evolving in instance space
• Unrelated parallel machine scheduling -- perspectives and progress
• A complex-networks view of hard combinatorial search spaces
• Global optimization test problems based on random field composition

This page was built for publication: What makes an optimization problem hard?.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q960453)