What makes an optimization problem hard?.

DOI10.1002/CPLX.6130010511zbMATH Open1455.90156OpenAlexW2279189561MaRDI QIDQ960453FDOQ960453

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

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 Keywords

combinatorial optimizationhardnessoptimization algorithm

Mathematics Subject Classification ID

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

Cited In (10)

• Theory versus practice in annealing-based quantum computing
• Connections in Networks: Hardness of Feasibility Versus Optimality
• Title not available (Why is that?)
• 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
• 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)