The Impact of Additional Information on Online and Parameterized Problems

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 competitiveness of the problem both with and without advice with respect to these parameters. The results obtained show that there is a tradeoff; the more restricted the value of a parameter is, the better the algorithm behaves. This tradeoff, not unexpected, serves to show that, for particular problems, finding an appropriate parameter that is restricted in most usual instances can help us get a better understanding of the complexity of the problem itself. Finally, we take a look at parameterized complexity. In particular, we give a model of reoptimization of parameterized problems and analyze several problems under this model. Reoptimization gives us essentially the solution to a similar instance and the goal is to adapt this solution to the instance we want to solve. Here, we see how much information the neighbouring solution is providing. The answer is that it depends on the problem and the measure of similarity. We find polynomial kernels under this setting, for some problems, that do not have polynomial kernels under some standard complexity-theoretic assumptions in the classical model. We also provide several lower bound results that show that some problems are just as hard under reoptimization as they are in their classical form