Algorithms for Integer Programming and Allocation

Rohwedder, Lars ORCID

The first part of the thesis contains pseudo-polynomial algorithms for integer linear programs (ILP). When certain parameters of an ILP are fixed, that is, they are treated as constants in the running time, it is possible to obtain algorithms with a running time that is pseudo-polynomial in the entries of the ILP’s matrix. We present a tight pseudo-polynomial running time for ILPs with a constant number of constraints. Furthermore, we study an extension of this model to MILPs (linear programs that contain both fractional and integer variables). Then we move to n-fold ILPs, a class of ILPs with block structured matrices. We present the first algorithm for n-folds, which is near-linear in the dimensions of the ILP. The second part is about scheduling in non-identical machine models, more precisely, restricted allocation problems. Here a set of jobs has to be allocated to a set of machines. However, every job has a subset of machines and may only be assigned to a machine from this subset. We consider the objectives of minimizing the makespan or maximizing the minimum load. We study the integrality gap of a particularly strong linear programming relaxation, the configuration LP, for variations of this problem. The integrality gap can be seen as a measure of strength of an LP relaxation. A local search technique can be used to bound this value. However, the proofs are generally non-constructive, i.e., they do not give an efficient approximation algorithm right away. We derive better upper bounds on the integrality gap of the problems Restricted Assignment, Restricted Santa Claus, and Graph Balancing. Furthermore, we give the first (constructive) quasi-polynomial time approximation algorithm for Restricted Assignment with an approximation ratio strictly less than 2.

Der erste Teil der Thesis umfasst pseudopolynomielle Algorithmen für ganzzahlige lineare Programme (ILP). Wenn bestimmte Parameter eines ILPs fixiert sind, d.h. sie werden in der Laufzeit als Konstanten betrachtet, dann ist es möglich Algorithmen zu entwerfen, deren Laufzeit pseudopolynomiell in dem größten absoluten Wert eines Eintrags der Matrix des ILPs ist. Ein Ergebnis, das wir präsentieren, ist eine scharfe Schranke für die pseudopolynomielle Laufzeit, die nötig ist um ein ILP mit konstant vielen Bedingungen zu lösen. Danach befassen wir uns mit n-fold ILPs, eine Klasse von ILPs, deren matrix eine Blockstruktur besitzt. Wir geben den ersten Algorithmus für n-folds an, dessen Laufzeit gleichzeitig nahezu linear in der Dimension des ILPs ist. Der zweite Teil handelt von nicht-identischen (heterogenen) Maschinen Modellen, genauer gesagt restricted allocation problems. Hier soll eine Menge von Jobs auf eine Menge von Maschinen verteilt werden. Jeder Job darf aber nur auf bestimmte Maschinen zugewiesen werden. Wir betrachten als Zielfunktionen sowohl die Minimierung des Makespans als auch die Maximierung der minimalen Last einer Maschine. Wir untersuchen den integrality gap einer besonders starken LP Relaxierung, dem Konfigurations LP, für Variationen dieses Problems. Der integrality gap kann als Maß für die Stärke einer LP Relaxierung gesehen werden. Über ein Argument mittels einer lokalen Suche wird dieser Wert beschränkt. Jedoch sind die Beweise typischerweise nicht konstruktiv, d.h. sie implizieren nicht direkt effiziente Approximationsalgorithmen. Wir beweisen neue obere Schranken an den integrality gap für die Probleme Restricted Assignment, Restricted Santa Claus und Graph Balancing. Desweiteren präsentieren wir den ersten (konstruktiven) Quasipolynomialzeit Approximationsalgorithmus für das Restricted Assignment Problem mit Approximationsrate echt kleiner als 2.

Zitieren

Zitierform:

Rohwedder, Lars: Algorithms for Integer Programming and Allocation.

Rechte

Nutzung und Vervielfältigung:
Keine CC Lizenz (es gilt das deutsche Urheberrecht)

Export