Faster min–max resource sharing in theory and practice
Faster min–max resource sharing in theory and practice
复制标题
理论和实践中更快的最小最大资源共享
DOI：
10.1007/s12532-011-0023-y
复制
发表时间：
2011
影响因子：
6.3
通讯作者：
J. Vygen
中科院分区：
文献类型：
--
作者：
D. Müller;K. Radke;J. Vygen
We consider the (block-angular) min–max resource sharing problem, which is defined as follows. Given finite setsof resources andof customers, a convex set, called block, and a convex functionfor every, the task is to findapproximately attaining $${\lambda^*:=\inf\{\max_{r\in\mathcal{R}}\sum_{c\in\mathcal{C}}(g_c(b_c))_r \mid b_c\in\mathcal{B}_c\ (c\in\mathcal{C})\}}$$. As usual we assume thatgccan be computed efficiently and we have a constantσ≥ 1 and oracle functions, called block solvers, which forandreturn an elementwith. We describe a simple algorithm which solves this problem with an approximation guaranteeσ(1 +ω) for anyω> 0, and whose running time isfor 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.
登录
查看更多内容
DOI：
--
发表时间：
1996
期刊：
影响因子：
--
作者：
J. Villavicencio;M. Grigoriadis
通讯作者：
M. Grigoriadis
优化全球布线的产量
DOI：
--
发表时间：
2006
期刊：
International Conference on Computer Aided Design
影响因子：
--
作者：
D. Müller
通讯作者：
D. Müller
通过少量的树度量来近似有限度量
DOI：
10.1109/sfcs.1998.743488
发表时间：
1998
期刊：
Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)
影响因子：
--
作者：
M. Charikar;C. Chekuri;Ashish Goel;S. Guha;Serge A. Plotkin
通讯作者：
Serge A. Plotkin
具有多块和耦合约束的凸规划的快速逼近方案
影响因子：
3.1
作者：
M. Grigoriadis;L. Khachiyan
通讯作者：
L. Khachiyan
影响因子：
1.7
作者：
M. Grigoriadis;L. Khachiyan
通讯作者：
L. Khachiyan