Open access

Author

Date

2019Type

- Doctoral Thesis

ETH Bibliography

yes
Altmetrics

Abstract

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. Show more

Permanent link

https://doi.org/10.3929/ethz-b-000384926Publication status

publishedExternal links

Search print copy at ETH Library
Publisher

ETH ZurichSubject

Online algorithms; Parameterized complexity; Reoptimization; k-Server problem; Coloring; Disjoint path allocation; Connected Vertex CoverOrganisational unit

03666 - Hromkovic, Juraj (emeritus) / Hromkovic, Juraj (emeritus)
More

Show all metadata
ETH Bibliography

yes
Altmetrics