Competitive Analysis for Incremental Maximization
David Michael Weckbecker
Die Aufgabe in der inkrementellen Maximierung ist es, im Laufe der Zeit eine Lösung aufzubauen, die den Wert einer gegebenen monotonen Zielfunktion maximiert. Dabei fügt man der Lösung ein Element nach dem anderen hinzu, ohne zu wissen, wie viele Elemente letztendlich in der Lösung enthalten sein dürfen. Diese Information wird erst in dem Moment bekannt, in dem das letzte zulässige Element hinzugefügt wurde. Daher besteht das Ziel in der inkrementellen Maximierung darin, eine Reihenfolge anzugeben, in der die Elemente zu der Lösung hinzugefügt werden, sodass deren Wert zu jedem Zeitpunkt größtmöglich ist. In dieser Arbeit befassen wir uns mit der kompetitiven Analyse dieses Problems und beweisen obere und untere Schranken für den kompetitiven Faktor dieses Problems.
Wir beweisen Schranken an den kompetitiven Faktor des greedy Algorithmus für eine große Klasse von Zielfunktionen, die mehrere bekannte Klassen aus der Literatur vereint. Über den greedy Algorithmus hinaus analysieren wir mehrere Skalierungsalgorithmen für das Problem unter der Annahme, dass die Zielfunktion accountable ist und geben strikte Schranken für deren kompetitiven Faktor an. Um einen besseren kompetitiven Faktor zu zeigen, führen wir eine randomisierte Variante eines Skalierungsalgorithmus ein und beweisen Schranken für den randomisierten kompetitiven Faktor des Problems der inkrementellen Maximierung mit einer Zielfunktion, die accountable ist. Wir führen eine Kontinuisierungstechnik ein und verwenden sie, um eine verbesserte untere Schranke an den kompetitiven Faktor für inkrementellen Maximierung zu zeigen, wenn die Zielfunktion accountable ist. Mit dem Ziel, den kompetitiven Faktor für größere Funktionenklassen zu beschränken, lockern wir die Eigenschaft der accountability und zeigen Schranken an den kompetitiven Faktor, wenn die Zielfunktion beta-accountable ist. Diese neue Klasse enthält beispielsweise subadditive Zielfunktionen. Abchließlend verallgemeinern wir das inkrementelle Maximierungsproblem, indem wir eine unbekannte Knapsack-Beschränkung anstelle einer unbekannten Kardinalitätsbeschränkung betrachten. Wir beweisen Schranken für den strikten und nicht-strikten kompetitiven Faktor dieses Problems, wenn die Zielfunktion fraktional subadditiv ist.