Next: Clustering
Up: Randomisierte Algorithmen
Previous: Das Component Commonality Problem
Auf diesem Gebiet wurden zwei sehr einfache Techniken entwickelt, eine
lineare Funktion über einer konvexen Menge zu optimieren. Die erste ist
ein deterministischer Algorithmus, der auf der Gradientenmethode basiert.
Die zweite ist ein randomisierter Algorithmus, der kleine lokale und
zufällige Änderungen in jedem Schritt durchführt. Die zweite Methode
kann benutzt werden, wenn die Menge nur durch ein Membership-Orakel
beschrieben ist, während die erste Methode etwas ähnliches wie ein
Separationsorakel erfordert. Wir entwickelten eine geeignete Definition
von smooth sets und waren in der Lage nachzuweisen, daß beide Algorithmen
nahezu optimale Lösungen in polynomieller Zeit liefern.
Diese Optimierungsmethode hat weitreichende Anwendungen in der
Linearen Optimierung und Stochastischen Optimierung,
wo die relevanten Mengen in der Tat smooth
und daher unsere Algorithmen anwendbar sind. Trotz ihrer simplen
Beschreibung liefern sie in vielen Fällen
die beste bisher bekannte Zeitkomplexität.
Webmaster<www@zpr.uni-koeln.de>
1999-07-28