In the first part of the talk, we revisit the (block-angular) min-max resource sharing problem, a well-known generalization of fractional packing and the maximum concurrent flow problem. It consists of finding a resource allocation for every customer such that the maximum resource usage is minimized. Resource sharing has several applications in VLSI design; among others, it is used to model the global routing problem.
We improve upon the currently fastest known FPTAS in various ways—surpassing the previously best-known running times for both the primal and dual problem—and show that the second-highest entry of the computed solution is approximately minimal.
In the second part of the talk, we introduce a novel usage model for tile-internal wire capacity in global routing, capturing local congestion more accurately than existing methods. We present new algorithms tailored to this usage model and discuss experimental results on real-world microprocessors, demonstrating its superiority over a state-of-the-art traditional global router.