On Algorithms for Multidimensional Packing Problems and on the Complexity of higher dimensional Knapsack

This thesis consists of two parts. In the first half we consider a range of so called online problems. In an online setting we are not given all informations of our input instance immediately. Instead we receive informations over time and algorithms have to handle not only the given instance at a specific time, but also the lack of information and an unknown future.

We consider a slightly relaxed setting where the solution we generate is not fixed but can be altered. We do not allow arbitrary repacking. We measure objects by some size criteria and allow repacking based on the total size of arrived or departed objects.
 
We introduce a framework that uses two algorithms, one from the offline world and one from the online world. By alternating these two algorithm we are able to achieve competitive ratios close to the approximative solution of known offline algorithms, while keeping necessary amotized migration small.

The second half of this thesis concerns itself with the multidimensional Knapsack problem and its connection to the (max,+)-convolution problem. We show that a conditional lower bound from the one-dimensional case can be generalized to higher dimensions. This implies that if and only if (max,+)-convolution in higher dimension can not be solved in sub-quadratic time, that even knapsack can not be solved in time that is sub-quadratic in the number of knapsack capacities.

We complement these results with algorithms that also abuse the connection between Knapsack and Convolution. We give a new algorithm that solves higher dimensional knapsack using one-dimensional convolution and carry over these results in order solve general Integer Linear Programs as well. Finally we also give an algorithm to solve Malleable Job Scheduling.

Rechte

Nutzung und Vervielfältigung:

Keine Lizenz. Es gelten die Bestimmungen des deutschen Urheberrechts (UrhG).

Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.