Alexander Sieber

• During the last couple of years, there has been a variety of publications on the topic of minimum quantity constraints. In general, a minimum quantity constraint is a lower bound constraint on an entity of an optimization problem that only has to be fulfilled if the entity is “used” in the respective solution. For example, if a minimum quantity \(q_e\) is defined on an edge \(e\) of a flow network, the edge flow on \(e\) may either be \(0\) or at least \(q_e\) units of flow. Minimum quantity constraints have already been applied to problem classes such as flow, bin packing, assignment, scheduling and matching problems. A result that is common to all these problem classes is that in the majority of cases problems with minimum quantity constraints are NP-hard, even if the problem without minimum quantity constraints but with fixed lower bounds can be solved in polynomial time. For instance, the maximum flow problem is known to be solvable in polynomial time, but becomes NP-hard once minimum quantity constraints are added. In this thesis we consider flow, bin packing, scheduling and matching problems with minimum quantity constraints. For each of these problem classes we provide a summary of the definitions and results that exist to date. In addition, we define new problems by applying minimum quantity constraints to the maximum-weight b-matching problem and to open shop scheduling problems. We contribute results to each of the four problem classes: We show NP-hardness for a variety of problems with minimum quantity constraints that have not been considered so far. If possible, we restrict NP-hard problems to special cases that can be solved in polynomial time. In addition, we consider approximability of the problems: For most problems it turns out that, unless P=NP, there cannot be any polynomial-time approximation algorithm. Hence, we consider bicriteria approximation algorithms that allow the constraints of the problem to be violated up to a certain degree. This approach proves to be very helpful and we provide a polynomial-time bicriteria approximation algorithm for at least one problem of each of the four problem classes we consider. For problems defined on graphs, the class of series parallel graphs supports this approach very well. We end the thesis with a summary of the results and several suggestions for future research on minimum quantity constraints.
• Im Laufe der letzten Jahre sind zahlreiche Veröffentlichungen erschienen, die sich mit dem Thema Minimum-Quantity-Bedingungen befassen. Allgemein beschreibt eine Minimum- Quantity-Bedingung eine untere Schranke, die sich auf ein Objekt eines Optimierungsproblems bezieht. Diese untere Schranke muss nur dann erfüllt sein, wenn eine Lösung das jeweilige Objekt “nutzt”. Wenn zum Beispiel eine Minimum-Quantity \(q_e\) für eine Kante \(e\) eines Flussnetzwerks definiert ist, darf der Fluss auf dieser Kante entweder \(0\) oder mindestens \(q_e\) Flusseinheiten betragen. Minimum-Quantity-Bedingungen wurden bereits auf Problemklassen wie Fluss-, Behälter-, Assignment-, Scheduling- und Matchingprobleme angewendet. Für all diese Problemklassen gilt, dass die meisten Probleme mit Minimum-Quantity-Bedingungen NP-schwer sind, selbst wenn die Probleme ohne Minimum-Quantity-Bedingungen aber mit festen unteren Schranken in polynomieller Zeit lösbar sind. Das Maximaler-Fluss-Problem ist bekanntermaßen in polynomieller Zeit lösbar, wird aber durch das Hinzufügen von Minimum-Quantity-Bedingungen NP-schwer. In dieser Arbeit betrachten wir Fluss-, Behälter-, Scheduling- und Matchingprobleme mit Minimum-Quantity-Bedingungen. Für jede dieser Problemklassen fassen wir die bisherigen Definitionen und Ergebnisse zusammen. Außerdem wenden wir Minimum- Quantity-Bedingungen auf das Maximum-Weight b-Matching-Problem und auf Open-Shop- Scheduling-Probleme an. Wir tragen zu jeder der vier Problemklassen neue Ergebnisse bei: Wir zeigen für mehrere bisher nicht betrachtete Probleme mit Minimum-Quantity- Bedingungen, dass diese NP-schwer sind. Wenn möglich, schränken wir NP-schwere Probleme weiter ein, um Spezialfälle zu erhalten, die in polynomieller Zeit gelöst werden können. Außerdem betrachten wir die Approximierbarkeit der Probleme: Für die meisten Probleme stellt sich heraus, dass diese, sofern nicht P=NP gilt, nicht in polynomieller Zeit approximiert werden können. Daher untersuchen wir auch die bikriterielle Approximierbarkeit, bei der Nebenbedingungen zu einem gewissen Grad verletzt sein dürfen. Dieser Ansatz erweist sich als sehr nützlich und wir sind in der Lage für mindestens ein Problem jeder Problemklasse einen bikriteriellen Approximationsalgorithmus mit polynomieller Laufzeit anzugeben. Für Probleme, die auf Graphen definiert sind, unterstützen seriell-parallele Graphen diesen Ansatz besonders gut. Abschließend fassen wir die Ergebnisse dieser Arbeit zusammen und schlagen einige Ansätze vor, die den Ausgangspunkt für die zukünftige Forschung in diesem Gebiet bilden könnten.