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.