Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Information Theory Workshop (ITW), IEEE, ISSN 1662-9019
National Category
Mathematics Computer Science
Identifiers
URN: urn:nbn:se:su:diva-112784DOI: 10.1109/ITW.2014.6970853OAI: oai:DiVA.org:su-112784DiVA: diva2:780780
Conference
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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 41 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf