Dissertation (Metadaten)
Titel:Approximation algorithms for min-max resource sharing and malleable tasks scheduling
 
Autor:Hu Zhang
 
URN:NBN:urn:nbn:de:gbv:8-diss-14081
 
Fakultät:Technische Fakultät
DDC Sachgebiet:004 Informatik
 
Datum der mdl. Prüfung:20.12.2004
 
Referent(in):Prof. Dr. Klaus Jansen
Korreferent(en) Korreferentin:Prof. Dr. Anand Srivastav, Prof. Dr. Denis Trystram
 
Beschreibung: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.
 
Schlagworte:Approximationsalgorithmus ; Betriebsmittelverwaltung ; Reihenfolgeproblem , Approximation Algorithms, Mathematical Programming, Combinatorial Optimization, Discrete Mathematics, Resource Sharing, Scheduling, Parallel Computing, Communication Networks, Wireless Networks, Malleable Tasks
 
Dokumente:
d1408.pdf (832 kB)    ZIP generieren   Details >>