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