Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
There are many open problems in the field of complexity. This means that, when analyzing the complexity of a specific computer science problem, we are often not satisfied with a standard complexity analysis of the problem. There are several known models that help us analyze the complexity of a problem in a more realistic setting or in a way that provides us more information than can be given by the classical complexity-theoretic tools. In this thesis, we take a look at several methods to help provide a more precise or adapted complexity analysis for some problems. The goal is always to find ways to measure the information content of the problem. We do this by adapting known models in several ways. First, we take a look at online problems, beginning with the k-server problem. In the advice complexity model, given an online instance for a problem, the algorithm is allowed access to an advice tape constructed by an all-knowing oracle. For the k-server problem, we give several results that provide a tradeoff between the advice complexity and the competitive ratio of this problem in several metric spaces. In particular, we focus on the Euclidean space and on the sphere, both in two dimensions and then generalizing the results to several dimensions. Then, we present the model of a randomized adversary, an alternative model to that of advice complexity, where instead of giving more power to the algorithm by giving it access to an advice tape, we restrict the power of the adversary by making it construct a set of instances, one of which will be chosen at random. In this model it is easier to find implementable upper bounds than in the advice complexity model, which is inherently nondeterministic but enables us to prove stronger lower bounds. We analyze the graph coloring problem in this model. The final online problem we analyze in this thesis is the weighted disjoint path allocation problem. For this problem, we take a look at several parameters, that might be reasonable for this problem, and we analyze the ...