Arbeitspapier

A guide to complexity theory in operations research

It is a well-known fact that there exists an ever increasing number of problems for which, despite the efforts of many inventive and persistent researchers, it seems virtually impossible to find efficient algorithms. In this Situation, the theory of computational complexity may provide helpful insight into how probable the existence of such algorithms is at all. Unluckily, some of its concepts can still be found to be used erroneously, if at all. For instance, it is a common misunderstanding that any problem that generalizes an NP-complete problem is NP-complete or NP-hard itself; indeed any such generalization could as well be exponential in the worst case, i.e. solvable with effort exponentially increasing in the size of the instances attempted. In this work we develop the basic concepts of complexity theory. While doing so, we aim at presenting the material in a way that emphasizes the correspondences between the kind of problems considered in Operations research and the formal problem classes which are studied in complexity theory.

Sprache
Englisch

Erschienen in
Series: Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel ; No. 381

Klassifikation
Management
Thema
Complexity Theory
Optimization Problems
NP-Complete
NP-Hard
NP-Easy
NP-Equivalent
Operations Research
Theorie

Ereignis
Geistige Schöpfung
(wer)
Schirmer, Andreas
Ereignis
Veröffentlichung
(wer)
Universität Kiel, Institut für Betriebswirtschaftslehre
ZBW – Leibniz Information Centre for Economics
(wo)
Kiel
(wann)
1995

Handle
Letzte Aktualisierung
10.03.2025, 11:45 MEZ

Datenpartner

Dieses Objekt wird bereitgestellt von:
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.

Objekttyp

  • Arbeitspapier

Beteiligte

  • Schirmer, Andreas
  • Universität Kiel, Institut für Betriebswirtschaftslehre
  • ZBW – Leibniz Information Centre for Economics

Entstanden

  • 1995

Ähnliche Objekte (12)