Tutte seminar - Jens Vygen

Tuesday, July 23, 2013 3:30 pm - 4:30 pm EDT (GMT -04:00)

Faster resource Sharing and VLSI Routing

Speaker: Jens Vygen
Affiliation: University of Bonn
Room: Mathematics and Computer Building (MC) 5158

Abstract:

We present a faster algorithm for the min-max resource sharing problem, generalizing the Garg-Könemann algorithm, and improving previous results by Grigoriadis and Khachiyan, Khandekar, and Jansen and Zhang.

We also show how this algorithm can be implemented efficiently and used to solve challenging global routing problems in chip design.
We obtain a near-optimal packing of millions of Steiner trees within a few hours.