Prof. Dr. Jens Vygen
Chip design is one of the most fascinating application areas of mathematics. One important task is routing. Interconnecting millions of sets of pins by wires is challenging because of the huge instance sizes and limited resources. The graphs can have billions of vertices. The space for laying out the wires and the time for propagating signals along wires are very limited. Moreover, even the simplest special cases of the routing problem are NP-hard.
We show how to model the routing problem by min-max resource sharing. This includes a novel way of modeling timing constraints. We present a simple combinatorial fully polynomial approximation scheme which is both faster and more general than all previous algorithms.
We implemented the algorithm; it is used for routing the most challenging chips in industry. Huge resource sharing instances are solved nearly optimally in less than an hour. The overall routing solution is far superior to those computed by industrial routing tools.
Datum: 04.06.2015, Raum: G03-106, Zeit: 17:00