Scheduling and Packing Problems : Algorithms and Complexity

Scheduling and packing problems are among the most studied in theoretical computer science. This is, in part, due to their high amount of practical applications, but also because they are interesting from a theoretical point of view: Most of these problems are NP-hard, so we cannot expect to solve all instances in polynomial time. The goal of parameterized complexity - and this thesis - is to find out exactly what makes these problems difficult to solve and to identify special cases that can be solved efficiently. One part of this is finding algorithms with running times that are efficient when certain input parameters are small. The other part is to show that some running times are impossible under plausible assumptions. 

In particular, we use parameterized reductions to show running time lower bounds for many scheduling and packing problems. Some of these suggest the optimality of existing algorithms from the literature, while others leave room for improvement. For one problem that falls into the latter case, we improve a classical dynamic programming algorithm so that its running time is likely optimal. 

For load balancing problems on uniform machines, we obtain a state-of-the-art running time, but with an entirely different approach than other algorithms, namely a combination of dynamic programming and divide-and-conquer. In some cases, this new algorithm is even faster than previous algorithms.

Due to their similar structure, many scheduling and packing problems can be described as finding a point in the intersection of a polyhedron and one (or more) integer cone(s). We improve the state-of-the-art algorithms for solving such problems, resulting in new parameterized algorithms for plenty of scheduling and packing problems. 

Finally, we also show a connection between identical and uniform machines, results about the structure of optimal solutions for job sequencing and some kernelization algorithms.

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.