Cost Preserving Dependent Rounding for Allocation Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915261205970944 |
|---|---|
| author | Rohwedder, Lars Rouhani, Arman Wennmann, Leo |
| author_facet | Rohwedder, Lars Rouhani, Arman Wennmann, Leo |
| contents | We present a dependent randomized rounding scheme, which rounds fractional solutions to integral solutions satisfying certain hard constraints on the output while preserving Chernoff-like concentration properties. In contrast to previous dependent rounding schemes, our algorithm guarantees that the cost of the rounded integral solution does not exceed that of the fractional solution. Our algorithm works for a class of assignment problems with restrictions similar to those of prior works.
In a non-trivial combination of our general result with a classical approach from Shmoys and Tardos [Math. Programm.'93] and more recent linear programming techniques developed for the restricted assignment variant by Bansal, Sviridenko [STOC'06] and Davies, Rothvoss, Zhang [SODA'20], we derive a O(log n)-approximation algorithm for the Budgeted Santa Claus Problem. In this new variant, the goal is to allocate resources with different values to players, maximizing the minimum value a player receives, and satisfying a budget constraint on player-resource allocation costs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_08267 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cost Preserving Dependent Rounding for Allocation Problems Rohwedder, Lars Rouhani, Arman Wennmann, Leo Data Structures and Algorithms We present a dependent randomized rounding scheme, which rounds fractional solutions to integral solutions satisfying certain hard constraints on the output while preserving Chernoff-like concentration properties. In contrast to previous dependent rounding schemes, our algorithm guarantees that the cost of the rounded integral solution does not exceed that of the fractional solution. Our algorithm works for a class of assignment problems with restrictions similar to those of prior works. In a non-trivial combination of our general result with a classical approach from Shmoys and Tardos [Math. Programm.'93] and more recent linear programming techniques developed for the restricted assignment variant by Bansal, Sviridenko [STOC'06] and Davies, Rothvoss, Zhang [SODA'20], we derive a O(log n)-approximation algorithm for the Budgeted Santa Claus Problem. In this new variant, the goal is to allocate resources with different values to players, maximizing the minimum value a player receives, and satisfying a budget constraint on player-resource allocation costs. |
| title | Cost Preserving Dependent Rounding for Allocation Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.08267 |