ISSN:
1436-6304
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Das Ellipsoidverfahren ist das erste bekannte Verfahren, das lineare und konvexe Optimierungsprobleme im Sinne der Komplexitätstheorie effizient löst. Mithilfe eines einfachen Rechnermodells führen wir kurz einige zum Verständnis notwendige Begriffe der Komplexitätstheorie ein und geben anschließend einen Überblick über die algorithmischen Vorläufer, die zur Entwicklung des Ellipsoidverfahrens geführt haben. Wir beschreiben die grundlegende geometrische Idee sowie eine Basisversion des Verfahrens, für die wir den Nachweis führen, daß sie lineare Programme im komplexitätstheoretischen Sinne effizient löst. Wir diskutieren einige Modifikationen der Basisversion und skizzieren die algorithmische Äquivalenz von Optimierung und Separation, die auf der Ellipsoidmethode beruht. Anhand eines Beispiels erläutern wir, wie diese Äquivalenz zu einem einheitlichen Modell effizienter Methoden geführt hat, das es erlaubte, weitere, effizient lösbare Probleme zu entdecken.
Notes:
Summary The ellipsoid method is the first known algorithm which in the sense of computational complexity solves linear and convex programming problems efficiently. Based on a simple computational model we introduce some notions from complexity theory and survey the historical antecessors which led to the development of the ellipsoid method. We discribe the fundamental geometric idea as well as a basic version of the algorithm and prove that this basic version gives an efficient algorithm for linear programming problems. We discuss some modifications of the basic method and outline the algorithmic equivalence of optimization and separation which is a consequence of the ellipsoid algorithm. By means of an example we show how this equivalence has led to a unifying framework for efficient algorithms which allowed to discover further efficiently solvable problems.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01720281
