Thomas Rothvoss did his PhD in Mathematics in 2009 at EPFL in
Switzerland under Friedrich Eisenbrand.
Then he was a PostDoc at MIT working with Michel Goemans. Since January
2014 he is Assistant Professor at the University of Washington, Seattle.
He was (co-)winner of the best paper awards at STOC 2010, SODA 2014 and
STOC 2014.
He received an Sloan Research Fellowship, an NSF CAREER award and a
Packard Fellowship.

AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

Public Audience

English

60 Minutes

Saarbrücken

One of the fundamental NP-hard problems in combinatorial optimization is
Bin Packing.
In terms of the best polynomial time approximation algorithm, we show
how to improve over
the previous best algorithm by Karmarkar and Karp from 1981 by a
quadratic factor.
The crucial techniques come from recent developments in discrepancy
theory, a
sub-field of combinatorics.

Then we will consider the special case that the number of different item
sizes is a constant. It had been open for at least 15 years, whether or
not this case is solvable
in polynomial time. We provide an affirmative answer to that.

The talk includes joint work with Michel X. Goemans and Rebecca Hoberg.

Petra Schaaf

5000

--email hidden

passcode not visible

logged in users only