A New Approximation Technique for Resource-Allocation Problems

2010/01/10 by Barna Saha, Aravind Srinivasan, Saha, Barna +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1001.1470

openalex publication_date 2010/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

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.

Citations

• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Dependent rounding and its applications to approximation algorithms

Related

• Cost Preserving Dependent Rounding for Allocation Problems
• Robust Assignments via Ear Decompositions and Randomized Rounding
• Santa Claus Schedules Jobs on Unrelated Machines
• Towards the distribution of the smallest matching in the Random Assignment Problem
• Dependent rounding and its applications to approximation algorithms