About the Structure and Sensitivity of Integer Linear Programs and their Application in Combinatorial Optimization

Klein, Kim-Manuel ORCID

In this thesis we investigate properties of integer linear programs (ILPs) and their algorithmic use. Our main focus are ILP-formulations that come from concrete algorthmic problems like the bin packing problem or the scheduling problem on identical machines. Especially for this kind of ILPs we study structural properties as well as properties for their sensitivity. As a result, we are able to answer open algorithmical questions in the area of approximation and parameterized complexity. In the context of sensitivity we analyze how much an ILP solution has to be adjusted when the parameters of the ILP change. There is a classical results by Cook et al. which gave bounds for that question when optimal solutions are considered. However, in this thesis we investigate the sensitivity of ILPs when approximate solutions are allowed, i.e. solutions that differ by a factor of at most (1+ \epsilon) from the optimum value. We could apply the obtained results to the online bin packing problem, when an approximation guarantee with ratio $1+ \epsilon$ has to be fulfilled and repacking of already assigned items (limited by the so called migration factor) is allowed. In the context of structural results, we prove the existence (assuming the ILP is feasible) of solutions of a certain class of ILPs with a certain simplified structure. Specifically, in this thesis, we prove structure properties for ILPs that arise from formulations of bin packing or scheduling problems and natural generalization of those formulations. Based on the those structure properties, we develop an efficient approximation scheme for the scheduling problem on identical machines with a running time of 2^{\tilde{O}(1/\epsilon)} + poly}(n) and furthermore, we develop a structure theorem, which is applied to the bin packing problem when the number of different item sizes d is bounded.

In dieser Dissertation werden Eigenschaften von ganzzahligen linearen Programmen (engl. integer linear programs, kurz: ILPs) untersucht. Von Interesse sind dabei hauptsächlich ILP-Formulierungen, welche sich aus dem Kontext von algorithmischen Problemstellungen ergeben, wie beispielsweise dem Bin Packing-Problem und dem Scheduling-Problem auf identischen Maschinen. Insbesondere für diese ILPs zeigen wir Strukturaussagen, sowie Aussagen über die Sensitivität und können so offene algorithmische Fragestellungen im Bereich von Approximation und parametrisierter Komplexität lösen. Im Kontext von Sensitivitätsaussagen wird untersucht, inwiefern Lösung des ILPs angepasst werden können, wenn sich die Parameter des ILPs leicht ändern. Ein klassisches Resultat von Cook u.a. gibt dabei für optimale Lösungen des ILPs Abschätzungen an. In dieser Arbeit betrachten wir Abschätzungen für die Senstivität wenn approximative Lösungen erlaubt sind, d.h. Lösungen deren Zielfunktionswert höchstens um einen Faktor 1+ \epsilon über dem optimalen Zielfunktionswert liegt. Diese Ergebnisse konnten wir auf das Online-Bin Packing-Problem anwenden, wenn eine approximative Lösung mit Güte 1+ \epsilon erreicht werden soll und in beschränktem Maße Items umgepackt werden dürfen. Im Kontext von Strukturaussagen wird in dieser Dissertation die Existenz von ILP-Lösungen bewiesen, welche eine bestimmte vereinfachte Struktur aufweisen. Insbesondere, konnten wir Strukturaussagen für ILPs entwickeln, welche sich aus Formulierungen des Bin Packing-Problems ergeben bzw. natürliche Verallgemeinerungen dieser Formulierung. Dadurch ist es uns zum einen gelungen ein effizientes Approximationsschemata für das Scheduling-Problem auf identischen Maschinen mit einer Laufzeit von 2^{\tilde{O}(1/\epsilon)} + poly(n) zu entwicklen und außerdem konnten wir eine Strukturaussage entwickeln, welche unter anderem Anwendung im Bin Packung-Problem fand, wenn die Anzahl der unterschiedlichen Itemgrößen d beschränkt ist.

Preview

Cite

Citation style:

Klein, Kim-Manuel: About the Structure and Sensitivity of Integer Linear Programs and their Application in Combinatorial Optimization. 2017.

Rights

Use and reproduction:
No CC License (german copyright law applies)

Export