ICS 2010
|
|
Welcome to ICS2010
Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, 342-357,
978-7-302-21752-7
Tsinghua University Press
We develop a rounding method based on random walks in polytopes, which leads to improved approximation algorithms and integrality gaps for several assignment problems that arise in resource allocation and scheduling. In particular, it generalizes the work of Shmoys & Tardos on the generalized assignment problem in two different directions, where the machines have hard capacities, and where some jobs can be dropped. We also outline possible applications and connections of this methodology to discrepancy theory and iterated rounding. Preview: 
|
Copyright 2009-2010, Institute for Computer Science, Tsinghua University, All Rights Reserved.