A New Approximation Technique for Resource-Allocation Problems

Details A New Approximation Technique for Resource-Allocation Problems A New Approximation Technique for Resource-Allocation Problems

2010-01-10

arxiv.org/abs/1001.1470v1

Computer Science

Data Structures and Algorithms

Proceedings of Innovations in Computer Science (ICS) 2010

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A New Approximation Technique for Resource-Allocation Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A New Approximation Technique for Resource-Allocation Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A New Approximation Technique for Resource-Allocation Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-128142