Change search
ReferencesLink to record
Permanent link

Direct link
Can we measure the difficulty of an optimization problem?
Stockholm University, Faculty of Science, Department of Mathematics.ORCID iD: 0000-0002-7168-4871
2014 (English)Conference paper (Other academic)
Abstract [en]

Can we measure the difficulty of an optimization problem? Although optimization plays a crucial role in modernscience and technology, a formal framework that puts problemsand solution algorithms into a broader context has not beenestablished. This paper presents a conceptual approach which gives a positive answer to the question for a broad class of optimization problems. Adopting an information and computational perspective, the proposed framework builds upon Shannon and algorithmic information theories. As a starting point, a concrete model and definition of optimization problems is provided. Then, a formal definition of optimization difficulty is introduced which builds upon algorithmic information theory. Following an initial analysis, lower and upper bounds on optimization difficulty are established. One of the upper-bounds is closely related to Shannon information theory and black-box optimization. Finally, various computational issues and future research directions are discussed.

Place, publisher, year, edition, pages
2014. 356-360 p.
, Information Theory Workshop (ITW), IEEE, ISSN 1662-9019
National Category
Mathematics Computer Science
URN: urn:nbn:se:su:diva-112784DOI: 10.1109/ITW.2014.6970853OAI: diva2:780780
IEEE Information Theory Workshop (ITW)
Available from: 2015-01-15 Created: 2015-01-15 Last updated: 2015-05-26Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Everitt, Tom
By organisation
Department of Mathematics
MathematicsComputer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 36 hits
ReferencesLink to record
Permanent link

Direct link