ISBN 9783843934343

978-3-8439-3434-3, Reihe Mathematik

Michael Hopf
Algorithms and Complexity for Scheduling and Packing Problems

183 Seiten, Dissertation Technische Universität Kaiserslautern (2017), Hardcover, A5

Zusammenfassung / Abstract

Scheduling and packing problems are two of the most important and most studied classes of problems in discrete optimization since they are both of high practical significance and of theoretical interest. In the last decades, they emerged to be the playground for many novel algorithmic ideas that yield exact or approximate solutions for these problems. It is rightful to say that their study advanced the fields of complexity and approximation algorithms and promises to be a major cornerstone in the further development of the theory of optimization.

In this thesis, we investigate extensions and variations of known scheduling and packing problems and provide results concerning their computational complexity and approximability. In particular, we analyze these problems from the point of view of revenue management. In multistage scheduling, one seeks to find a solution of a sequential scheduling process which naturally occurs, e.g., in supply chains. The main frameworks that we use for our analysis are online optimization and game theory. We develop algorithms and prove guarantees on their performance. Then, we consider each participant of the scheduling process as a selfish player who tries to maximize her own profit, and establish results on game theoretical equilibria.

Moreover, we investigate a variant of the Multiple Knapsack Problem in the context of assortment planning. Here, a retailer with multiple chain stores needs to specify her offered assortment. Again, we provide approximation algorithms and complexity results. Of particular theoretical interest is an algorithm forged from three auxiliary algorithms. Whereas these lead poor results individually, we are able to prove that the emerging one yields a good performance bound.

Subsequently, we consider another packing problem that originates from scheduling television advertisements in the broadcasting industry. Among our algorithmic and complexity findings, we want to emphasize the development of an approximation scheme that yields close to optimal solutions.

Beyond these problems, we also prove the hardness of approximation of a variant of the classical Shortest Path Problem where the objective is quadratic instead of linear.