Diedrich, Florian
[VerfasserIn]
;
Jansen, Klaus
[MitwirkendeR];
Trystram, Denis
[MitwirkendeR]
Approximation algorithms for linear programs and geometrically constrained packing roblems ; Algorithmes d'approximation pour des programmes linéaires et les problèmes de Packing avec des contraintes géometriques
Titel:
Approximation algorithms for linear programs and geometrically constrained packing roblems ; Algorithmes d'approximation pour des programmes linéaires et les problèmes de Packing avec des contraintes géometriques
Beteiligte:
Diedrich, Florian
[VerfasserIn]
Erschienen:
MACAU: Open Access Repository of Kiel University, 2009
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
In this thesis we approach several problems with approximation algorithms; these are feasibility problems as well as optimization problems. In Chapter 1 we give a brief introduction into the general paradigm of approximation algorithms, motivate the problems, and give an outline of the thesis. In Chapter 2, we discuss two algorithms to approximately generate a feasible solution of the mixed packing and covering problem which is a model from convex optimization. This problem includes a large class of linear programs. The algorithms generate approximately feasible solutions within O(M(ln M+epsilon^{-2} ln epsilon^{-1})) and O(M epsilon{-2} ln (M epsilon^{-1}))$ iterations, respectively, where in each iteration a block problem which depends on the specific application has to be solved. Both algorithms, applied to linear programs, can result in column generation algorithms. In Chapter 3, we implement an algorithm for the so-called max-min-resource sharing problem. This is a certain convex optimization problem which, similar to the problem in Chapter 1, includes a large class of linear programs. The implementation, which is included in the appendix, is done in C++. We use the implementation in the context of an AFPTAS for Strip Packing in order to evaluate dynamic optimization of a parameter in the algorithm, namely the step length used for interpolation. We compare our choice to the static step length proposed in the analysis of the algorithm and conclude that dynamic optimization of the step length significantly reduces the number of iterations. In Chapter 4, we study two closely related scheduling problems, namely non-preemptive scheduling with fixed jobs and scheduling with non-availability for sequential jobs on m identical machines under the makespan objective, where m is constant. For the first problem, which does not admit an FPTAS unless P=NP, we obtain a new PTAS. For the second problem, we show that a suitable restriction (namely the permanent availability of one machine) is necessary to obtain a bounded ...