A new approximation technique for resource‐allocation problems. Issue 4 (30th January 2018)

• Record Type: Journal Article
• Authors: Saha, Barna; Srinivasan, Aravind
• Is Part Of: Random structures & algorithms. Volume 52:Issue 4(2018)
• Page Start: 680
• Page End: 715
• Publication Date: 2018-01-30
• Subjects: approximation algorithms -- integrality gap -- randomized algorithms -- rounding -- Scheduling; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20756
• Languages: English
• ISSNs: 1042-9832

Abstract

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 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.