Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Modern algorithms for Bin packing
Speaker:Thomas Rothvoss
coming from:University of Washington, Seattle
Speakers Bio: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.
Event Type:INF Distinguished Lecture Series
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Language:English
Date, Time and Location
Date:Tuesday, 15 May 2018
Time:10:00
Duration:60 Minutes
Location:Saarbr├╝cken
Building:E1 4
Room:024
Abstract
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.
Contact
Name(s):Petra Schaaf
Phone:5000
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
Created:
Petra Schaaf/AG5/MPII/DE, 05/07/2018 01:33 PM
Last modified:
halma/MPII/DE, 11/07/2018 04:52 PM
  • Petra Schaaf, 05/07/2018 01:40 PM -- Created document.