We won’t be posting all talks, but there is a calendar you can add if you want to hear about them all. These are open to all students.
http://www.cs.washington.edu/events/colloquia
Our first CSE talk of the 2014-15 academic year – this Thursday, 10/2/14
UNIVERSITY OF WASHINGTON
Computer Science and Engineering
COLLOQUIUM
SPEAKER: Thomas Rothvoss, UW Mathematics
TITLE: Better algorithms for Bin packing
DATE: Thursday, October 2, 2014
TIME: 3:30pm
PLACE: EEB-105
HOST: James Lee
ABSTRACT:
One of the fundamental NP-hard problems in combinatorial optimization is
Bin Packing.
In terms of the best polynomial time approximation algorithm, we improve
over the previous best algorithm by Karmarkar and Karp from 1981 by a
quadratic factor.
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 will give an affirmative answer to that.
This is joint work with Michel X. Goemans.
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 in the Mathematics department at UW.
He was (co-)winner of the best paper awards at STOC 2010, SODA 2014 and
STOC 2014.
Refreshments to be served in room prior to talk.
*NOTE* This lecture will be broadcast live via the Internet. See
http://www.cs.washington.edu/
Email: talk-info@cs.washington.edu
Info: http://www.cs.washington.edu/
(206) 543-1695
The University of Washington is committed to providing access, equal
opportunity and reasonable accomodation in its services, programs,
activities, education and employment for individuals with disabilities.
To request disability accommodation, contact the Disability Services
Office at least ten days in advance of the event at: (206) 543-6450/V,
(206) 543-6452/TTY, (206) 685-7264 (FAX), or email at
dso@u.washington.edu.
______________________________