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.

https://tuprints.ulb.tu-darmstadt.de/26447