What makes an optimization problem hard?.
Summary: We address the question: ``Are some classes of combinatorial optimization problems intrinsically harder than others, without regard to the algorithm one uses, or can difficulty only be assessed relative to particular algorithms? We provide a measure of the hardness of a particular optimization problem for a particular optimization algorithm and present two algorithm-independent quantities that use this measure to provide answers to our question. In the first of these we average hardness over all possible algorithms and show that according to this quantity, there are no distinctions between optimization problems. In this sense no problems are intrinsically harder than others. For the second quantity, rather than average over all algorithms, we consider the level of hardness of a problem (or class of problems) for the associated optimal algorithm. By this criteria there are classes of problems that are intrinsically harder than others.
- Measuring instance difficulty for combinatorial optimization problems
- Theory versus practice in annealing-based quantum computing
- Generating new test instances by evolving in instance space
- Connections in Networks: Hardness of Feasibility Versus Optimality
- Exploring the role of graph spectra in graph coloring algorithm performance
- Discovering the suitability of optimisation algorithms by learning from evolved instances
- A complex-networks view of hard combinatorial search spaces
- scientific article; zbMATH DE number 4001485 (Why is no real title available?)
- Unrelated parallel machine scheduling -- perspectives and progress
- What Is Important About the No Free Lunch Theorems?
- 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)
