Extensions of secretary problems towards submodular objectives and temporal arrival

Aachen (2017) [Doktorarbeit]

Seite(n): 1 Online-Ressource (viii, 87 Seiten) : Illustrationen, Diagramme

Kurzfassung

Online-Algorithmen treffen unveränderliche Entscheidungen, bevor alle relevanten Informationen über ein Problem verfügbar sind. Praktische Anwendungen sind z. B. Online-Routing- oder Schedulingprobleme. Online-Algorithmen werden häufig als Spiel zwischen dem Online-Algorithmus und einem böswilligem Gegenspieler betrachtet. Hierbei wird die Probleminstanz vom Gegner so konstruiert, dass der Online-Algorithmus sich möglichst ungünstig verhält. In der Praxis ist diese Sichtweise allerdings häufig zu pessimistisch. Daher entwickeln wir Algorithmen für Probleme, in denen der Gegner nur die Elemente der Instanz festlegt, aber nicht die Reihenfolge, in der sie dem Algorithmus präsentiert werden. Stattdessen ist die Ankunftsreihenfolge in den hier betrachteten Problem uniform zufällig. Probleme dieser Art werden auch Secretary Probleme genannt. In allen in dieser Dissertation betrachteten Problemen repräsentieren die Online-Daten Gegenstände oder Elemente, die der Online-Algorithmus akzeptieren oder ablehnen kann. Wir bewerten unsere Algorithmen, indem wir die Kompetitivität der Algorithmen untersuchen. Hierbei vergleichen wir den erwarteten Wert, den der Onlinealgorithmus erreicht, mit dem Wert der optimalen Offline-Lösung und verbessern die bekannten Schranken für alle untersuchten Probleme.Im ersten technischen Teil der Arbeit betrachten wir submodulare Secretary Probleme. In diesen Problemen legt der Gegner eine submodulare Zielfunktion auf einer Menge von Elementen sowie kombinatorische Nebenbedingungen fest. Die Reihenfolge, in der die Elemente dem Algorithmus präsentiert werden, ist uniform zufällig. Das Ziel ist es, Elemente online auszuwählen, sodass die Zielfunktion maximiert wird, ohne dass eine Nebenbedingung verletzt wird.Der zweite technische Teil der Arbeit behandelt Temp Secretary Probleme. Bei diesem Typ von Problem ist die Zielfunktion linear und die Elemente kommen uniform über ein Zeitintervall verteilt an. In diesem Model ist die relative Ankunftsreihenfolge ebenfalls uniform zufällig, allerdings stehen außerdem exakte Ankunftszeitpunkte zur Verfügung. Diese Zeitinformationen können dann in temporalen Nebenbedingungen genutzt werden. Hierbei muss die Menge aller Elemente, die innerhalb eines gegebenen Zeithorizontes ausgewählt wurden, die Nebenbedingungen erfüllen.Unsere Algorithmen für beide Arten von Problemen sind sehr ähnlich. Zu jedem Zeitpunkt, wenn eine neue Entscheidung getroffen werden muss, berechnet der Online-Algorithmus eine optimale Offline-Lösung anhand all der Informationen, die zu dem Zeitpunkt bekannt sind. Diese lokale Lösung wird genutzt, um die Online-Entscheidung zu steuern. Bevor wir die technischen Details der beiden Problemtypen präsentieren, geben wir eineEinleitung in die genutzten algorithmischen Ideen und relevanten Beweistechniken.Als neuartiges Kriterium für Online-Algorithmen führen wir das Konzept von (alpha*c)-kompetitiven Algorithmen ein. Dabei ist c der bekannte erwartete Kompetitivitätsfaktor und alpha ist die Approximationsgarantie eines Algorithmus für die Offline-Variante des Problems. Falls die benötigte Rechenleistung keine Rolle spielt, dann ist alpha = 1. Andernfalls, falls der Algorithmus nur begrenzt viel Zeit oder Platz nutzen kann, dann ist alpha der Approximationsfaktor eines Offline-Algorithmus, der diese Beschränkungen einhält. Dadurch erhalten wir eine klare Trennung der komplexitätstheoretischen Schwierigkeit von der informationstheoretischen Schwierigkeit des Problems. Dies ist von besonderer Bedeutung für Online-Algorithmen mit submodularer Zielfunktion, da die Maximierung einer submodularen Funktion NP-schwer ist.

Autorinnen und Autoren

Autorinnen und Autoren

Tönnis, Andreas

Gutachterinnen und Gutachter

Unger, Walter
Peis, Britta
Rossmanith, Peter

Identifikationsnummern

  • REPORT NUMBER: RWTH-2017-02825