Premium
A new approximation technique for resource‐allocation problems
Author(s) -
Saha Barna,
Srinivasan Aravind
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20756
Subject(s) - rounding , bipartite graph , polytope , scheduling (production processes) , matching (statistics) , approximation algorithm , resource allocation , mathematical optimization , computer science , random walk , combinatorics , mathematics , discrete mathematics , computer network , operating system , graph , statistics
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 and Tardos on the generalized assignment problem to the setting where some jobs can be dropped. New concentration bounds for random bipartite matching are developed as well.