Mathematical Programming Computation, Volume 3, Issue 1, March 2011

Faster min–max resource sharing in theory and practice

Dirk Müller, Klaus Radke, Jens Vygen

We consider the (block-angular) min–max resource sharing problem, which is defined as follows. Given finite sets of resources and of customers, a convex set c, called block, and a convex function gc:cR+ for every c, the task is to find bcc (c) approximately attaining :=infmaxrc(gc(bc))rbcc (c) . As usual we assume that g c can be computed efficiently and we have a constant ? ? 1 and oracle functions fc:R+c, called block solvers, which for c and yR+ return an element bcc with ygc(bc)infbcygc(b). We describe a simple algorithm which solves this problem with an approximation guarantee ?(1 + ?) for any ? > 0, and whose running time is O((+)log(loglog+?2)) for any fixed ? ? 1, where ? is the time for an oracle call. This generalizes and improves various previous results. We also prove other bounds and describe several speed-up techniques. In particular, we show how to parallelize the algorithm efficiently. In addition we review another algorithm, variants of which were studied before. We show that this algorithm is almost as fast in theory, but it was not competitive in our experiments. Our work was motivated mainly by global routing in chip design. Here the blocks are mixed-integer sets (whose elements are associated with Steiner trees), and we combine our algorithm with randomized rounding. We present experimental results on instances resulting from recent industrial chips, with millions of customers and resources. Our algorithm solves these instances nearly optimally in less than two hours.

Full Text: PDF

Imprint and privacy statement

For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2023 by Zuse Institute Berlin (ZIB).