Hausdorff Forum July 14, 2017 - 14:15

Location: Lipschitz-Saal, Endenicher Allee 60

The previously announced lecture held by RĂ¼diger Schultz has been cancelled.

14:15 Jens Vygen (Uni Bonn): Resource Sharing, Routing, Chip-Design

Chip design is one of the most fascinating application areas of mathematics. After a brief overview we focus on routing, a key problem. The task is to interconnect millions of sets of pins by disjoint wires. This is difficult because 

(a) instance sizes are huge (graphs with billions of vertices),

(b) resources such as space and propagation time are very limited, and 

(c) even the simplest special cases are NP-hard. 

We show how to model routing by a very abstract problem, known as 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 previous algorithms. We implemented the algorithm and solve huge instances nearly optimally. The overall router is far superior to commercial routing tools and has been used for designing many of the most challenging chips.

15:15-15:45 Tea