Klein, Kim-Manuel
[Verfasser:in]
;
Jansen, Klaus
[Mitwirkende:r];
Skutella, Martin
[Mitwirkende:r]
About the Structure and Sensitivity of Integer Linear Programs and their Application in Combinatorial Optimization ; Über Struktur- und Sensitivitätsaussagen in Ganzzahligen Programmen und deren Anwendung in Kombinatorischer Optimierung
Titel:
About the Structure and Sensitivity of Integer Linear Programs and their Application in Combinatorial Optimization ; Über Struktur- und Sensitivitätsaussagen in Ganzzahligen Programmen und deren Anwendung in Kombinatorischer Optimierung
Beteiligte:
Klein, Kim-Manuel
[Verfasser:in]
Erschienen:
MACAU: Open Access Repository of Kiel University, 2017
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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 ...