14 documents found

Dissertation

Discrepancy of arithmetic structures

In discrepancy theory, we investigate how well a desired aim can be achieved. So typically we do not compare our solution with an optimal solution, but rather with an (idealized) aim. For example, in the declustering problem, we try to distribute data on parallel disks in such a way that all of a prespecified...
Dissertation

A QOBDD-based Approach to Simple Games

Simple games are a commonly used model for the analysis of voting systems in which each participant can vote “yes” or “no” and where the outcome is “yes” or “no” as well. Quasi-reduced and ordered binary decision diagrams, or QOBDDs for short, are well-known as compact representations for subsets of...
Dissertation

Algorithm Engineering for some Complex Practise Problems Exact Algorithms,...

This work deals with the design of exact algorithms and heuristics for complex optimization problems that origin from three practical applications and one classical combinatorial task. We obtain exact algorithms by modeling our problems in terms of mathematical optimization problems and applying suitable...
Dissertation

Probabilistic analysis of euclidean multi depot vehicle routing and related...

We consider a generalization of the classical traveling salesman problem: the multi depot vehicle routing problem (MDVRP). Let $D$ be a set of $k$ depots and $P$ be sets $n$ customers in $[0,1]^d$ with the usual Euclidean metric. A multi depot vehicle routing tour is a set of disjoint cycles such that...
Dissertation

Cubature formulas on wavelet spaces

keine engl.-spr. Zusammenfassung vh.
Dissertation

Efficient derandomization of the Lovász Local Lemma and applications to...

We use algorithmic versions of Lovasz Local Lemma (LLL) to deal with the following two packing type problems: (i) a particular kind of hypergraph coloring problem, and (ii) vector packing problem. The hypergraph coloring problem is connected to the resource constrained scheduling problem and vector packing...
Dissertation

Towards a unified approach to learning and adaptation

The aim of this thesis is to develop a system that enables autonomous and situated agents to learn and adapt to the environment in which they live and operate. In doing so, the system exploits both adaptation through learning and evolution. A unified approach to learning and adaptation, which combines...
Dissertation

Approximation algorithms for 2d packing problems

In this thesis we address such 2-dimensional packing problems as strip packing, bin packing and storage packing. These problems play an important role in many application areas, e.g. cutting stock, VLSI design, image processing, and multiprocessor scheduling. The larger part of work is devoted to the...
Dissertation

Randomized Approximation for the Matching and Vertex Cover Problem in Hypergraphs:...

This thesis studies the design and mathematical analysis of randomized approximation algorithms for the hitting set and b-matching problems in hypergraphs. We present a randomized algorithm for the hitting set problem based on linear programming. The analysis of the randomized algorithm rests upon the...
Dissertation

Games in Networks under Robustness, Locality, and Coloring Aspects

Decentralization is a key concept in modern networks, such as the Internet, social networks, or wireless phone or sensor networks. The systematic study of how networks are formed by a multitude of non-cooperative or only mildly cooperative players, is a vivid topic in Discrete Mathe- matics, Computer...
Dissertation

Approximation algorithms for min-max resource sharing and malleable tasks...

This thesis deals with approximation algorithms for problems in mathematical programming, combinatorial optimization, and their applications. We first study the min-max resource-sharing problem (the packing problem as the linear case) with $M$ nonnegative convex constraints on a convex set $B$, which...
Dissertation

Networks and distributed operation : the price of anarchy in non-atomic...

The price of anarchy is a measure for performance loss due to individuals operating in a distributed manner, i.e., without or with only limited central control or without or with only limited cooperation. In the first part, a network is given and used in a distributed manner, namely for multicast routing,...
Dissertation

Approximation and online algorithms in scheduling and coloring

In the last three decades, approximation and online algorithms have become a major area of theoretical computer science and discrete mathematics. Scheduling and coloring problems are among the most popular ones for which approximation and online algorithms have been analyzed. On one hand, motivated by...
Dissertation
CC BY 4.0

Positional and Detection Games

When it comes to the interaction of two ore more parties with individual aims, it’s all about ļ¬nding an appropriate strategy. In most cases, the individual aim boils down to detection of information about the general situation or about your opponents and improvement of your own position. This goal becomes...