Approximation algorithms for min-max resource sharing and malleable tasks scheduling

This thesis deals with approximation algorithms for problems in mathematical programming, combinatorial optimization, and their applications. We first study the min-max resource-sharing problem (the packing problem as the linear case) with $M$ nonnegative convex constraints on a convex set $B$, which is a class of convex programming. In general block solvers are required for solving the problems. We generalize the algorithm by Grigoriadis et al. to the case with only weak approximate block solvers. In this way we present an approximation algorithm that needs at most $O(M(\ln M+\epsilon^{-2}\ln\epsilon^{-1}))$ calls to the block solver for any given relative accuracy $\epsilon\in(0,1)$. It is the first bound independent of the data and the approximation ratio of the block solver. As applications of the min-max resource-sharing problem, we study the multicast congestion problem in communication networks and the range assignment problem in arbitrary ad-hoc networks. We present improved approximation algorithms for these problems. We also study the problem of scheduling malleable tasks with precedence constraints. We are given $m$ identical processors and $n$ tasks. For each task the processing time is a discrete function of the number of processors allotted to it. In addition, the tasks must be processed according to the precedence constraints. The goal is to minimize the makespan (maximum completion time) of the resulting schedule. We improve the previous best approximation algorithm with a ratio $3+\sqrt{5}\approx 5.236$ to $100/43+100(\sqrt{4349}-7)/2451\approx 4.730598$. Finally, we propose a new model for malleable tasks and develop an approximation algorithm for the scheduling problem with a ratio $100/63+100(\sqrt{6469}+13)/5481\approx 3.291919$. We also show that our results are very close to the best asymptotic one