000K  utf8
1100  $c2005
1500  eng
2050  urn:nbn:de:gbv:8-diss-14081
3000  Zhang, Hu
4000  Approximation algorithms for min-max resource sharing and malleable tasks scheduling$hChristian-Albrechts-Universität zu Kiel  [Zhang, Hu]
4030  Kiel$nChristian-Albrechts-Universität zu Kiel
4209  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.
4950  https://nbn-resolving.org/urn:nbn:de:gbv:8-diss-14081$xR$3Volltext$534
4961  https://macau.uni-kiel.de/receive/diss_mods_00001408
5051  004
5550  Approximation Algorithms
5550  Approximationsalgorithmus
5550  Betriebsmittelverwaltung
5550  Combinatorial Optimization
5550  Communication Networks
5550  Discrete Mathematics
5550  Malleable Tasks
5550  Mathematical Programming
5550  Parallel Computing
5550  Reihenfolgeproblem
5550  Resource Sharing
5550  Scheduling
5550  Wireless Networks