Approximation algorithms for linear programs and geometrically constrained packing roblems

Diedrich, Florian

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.

Cite

Citation style:

Diedrich, Florian: Approximation algorithms for linear programs and geometrically constrained packing roblems. 2009.

Rights

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

Export