PT Unknown
AU Diedrich, F
TI Approximation algorithms for linear programs and geometrically constrained packing roblems
PY 2009
PU Christian-Albrechts-Universität zu Kiel
WP https://macau.uni-kiel.de/receive/diss_mods_00003488
LA en
DE Lineare Programmierung; Optimierung; Scheduling; Packing; Implementierung; programmation linéaire; optimization; ordonnancement; implementation
AB 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 approximation ratio. For this restriction, which does not admit an FPTAS unless P=NP, we present
a PTAS; we also discuss the complexity of various special cases. In total, the results are basically best possible.
In Chapter 5, we continue the studies from Chapter 4 where now the number 
m of machines is part of the input, which makes the problem 
algorithmically harder. Scheduling with fixed jobs does not admit an  approximation ratio better than 3/2, unless P=NP; here we obtain an  approximation ratio of 3/2+epsilon for any epsilon>0. For  scheduling with non-availability, we require a constant percentage of the machines to be permanently available. This restriction also does not admit an approximation ratio better than 3/2 unless P=NP; we 
also obtain an approximation ratio of $3/2+\epsilon$ for any epsilon>0. With an interesting argument, the approximation ratio for both problems is 
refined to exactly 3/2. We also point out an interesting relation  of scheduling with fixed jobs to Bin Packing. As in Chapter 4, the results are in a certain sense best possible.
Finally, in Chapter 6, we conclude
with some remarks and open research problems.
PI Kiel
ER