Referent: Dipl.-Inform. Oliver Göbel
Titel: Online Resource Allocation on Stochastic Input Models
Abstract:
The characteristic of online algorithms is that the input is not given at once but it is revealed stepwise in rounds. An online algorithm must make irrevocable decisions upon the arrival of each input request and thus before the entire input is known. As these decisions are made under uncertainty about future requests, they may turn out as not optimal in the end. The established method is to analyze online algorithms under worst-case assumptions in terms of the competitive ratio. This is the relation of the optimal solution and the worst output of the online algorithm. For many online combinatorial optimization problems, however, there exist lower bounds which indicate that no online algorithms with non-trivial competitive ratio can be derived when all assumptions are worst-case. To cope with these optimization problems in a less restrictive and more realistic way, it is promising to relax various worst-case assumptions via including stochastic components into the model. As a consequence, several stochastic input models exist. They all ease single worst-case assumptions, but all in a different manner: where one model assumes a stochastic arrival of a worst-case input, another lets the input be stochastically but revealed in worst-case order. We continue with this approach and consider online optimization problems with stochastic inputs in this thesis. To this end, we do neither focus on one single optimization problem nor on one single input model.
Instead, we introduce a new unifying input model that allows us to bridge between several input models, and we consider different problems then. The first algorithm we design considers the online independent set problem, where the nodes of a graph arrive one after another and an edge appears when both nodes have been revealed. Our algorithm achieves a constant competitive factor. For the weighted problem statement, we can give a Ο(log n) competitive algorithm and complement this result by a lower bound showing that our algorithm is almost optimal. Possible applications of the independent set problem can be found in scheduling when a subset of jobs needs to be selected. Other problems in scheduling aim at sorting the jobs according to their significance. One of these settings is the online appointment scheduling problem, where the aim is to order online incoming jobs such that the weighted completion time is minimized. We also derive constant and Ο(log n)-competitive algorithms for different variants of this problem. Since the minimization objective does not allow to apply the unifying model immediately, we first consider the problem in the random-order model and draw connections to the other input models afterwards. In the secretary leasing problem that we investigate in the last chapter of this thesis, it is necessary to consider the problem over time. In the problem statements described so far, the input was revealed stepwise and the constraints were with respect to the global instance. This is significantly different in the secretary leasing problem, since there exist additional constraints regarding also the rounds where the input appears in. Among other results, we present a constant competitive online algorithm for this problem.
Es laden ein: Die Dozenten der Informatik