Competitive Analysis for Incremental Maximization

In incremental maximization, we are tasked with building up a solution over time by adding elements from a groundset one by one. We want to maximize the monotone objective value of the assembled solution. However, the information how many elements may be added to the final solution is only revealed when the last feasible element is added. Thus, the goal is to give an ordering in which to add the elements such that the value of the solution in each step is maximized. In this thesis, we investigate this problem in the sense of competitive analysis and present upper and lower bounds on the competitive ratio for various subclasses of this problem.

We prove bounds on the competitive ratio of the greedy algorithm for a broad class of objective functions that unifies several well-known classes from the literature. Beyond the greedy algorithm, we analyze multiple scaling algorithms for the problem setting with an accountable objective and give tight bounds on their competitive ratios. In order to further improve the competitive ratio, we introduce a randomized variant of a scaling algorithm and prove bounds on the randomized competitive ratio of incremental maximization with an accountable objective. We introduce a continuization technique and use it to show an improved lower bound on the competitive ratio of incremental maximization with an accountable objective function. In an attempt to capture more objective functions than only accountable ones, we relax this property and show bounds on the competitive ratio if the objective is beta-accountable. This new class captures objectives as, for example, subadditive ones. Lastly, we generalize the incremental maximization problem by considering an unknown knapsack constraint instead of an unknown cardinality constraint. We prove bounds on the strict and non-strict competitive ratio of this problem if the objective function is fractionally subadditive.

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.