A New Approximation Technique for Resource-Allocation Problems
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Resource Minimization Job Scheduling2009
- An improved approximation algorithm for vertex cover with hard capacitiesJournal of Computer and System Sciences, 2006
- A comment on scheduling two parallel machines with capacity constraintsDiscrete Optimization, 2005
- Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance GuaranteeJournal of Combinatorial Optimization, 2004
- An approximation algorithm for scheduling two parallel machines with capacity constraintsDiscrete Applied Mathematics, 2003
- A Factor 2 Approximation Algorithm for the Generalized Steiner Network ProblemCombinatorica, 2001
- An approximation algorithm for the generalized assignment problemMathematical Programming, 1993
- Approximation algorithms for scheduling unrelated parallel machinesMathematical Programming, 1990
- Global wire routing in two-dimensional arraysAlgorithmica, 1987
- Roth’s estimate of the discrepancy of integer sequences is nearly sharpCombinatorica, 1981