Smooth Sets

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.