Cycle Cancellation for Submodular Fractional Allocations and Applications
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911287693279232 |
|---|---|
| author | Chekuri, Chandra Kulkarni, Pooja Mehta, Ruta Vondrak, Jan |
| author_facet | Chekuri, Chandra Kulkarni, Pooja Mehta, Ruta Vondrak, Jan |
| contents | We consider discrete allocation problem where $m$ indivisible goods are to be divided among $n$ agents. When agents' valuations are additive, the well-known cycle cancelling lemma by Lenstra, Shmoys, and Tardos plays a key role in design and analysis of rounding algorithms.
In this paper, we prove an analogous lemma for the case of submodular valuations. Our algorithm removes cycles in the support graph of a fractional allocation while guaranteeing that each agent's value, measured using the multilinear extension, does not decrease.
We demonstrate applications of the cycle-canceling algorithm, along with other ideas, to obtain new algorithms and results for three well-studied allocation objectives: max-min (Santa Claus problem), Nash social welfare (NSW), and maximin-share (MMS). For the submodular NSW problem, we obtain a $\frac{1}{5}$-approximation; for the MMS problem, we obtain a $\frac{1}{2}(1-1/e)$-approximation through new simple algorithms. For various special cases where the goods are "small" valued or the number of agents is constant, we obtain tight/best-known approximation algorithms. All our results are in the value-oracle model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_21099 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cycle Cancellation for Submodular Fractional Allocations and Applications Chekuri, Chandra Kulkarni, Pooja Mehta, Ruta Vondrak, Jan Computer Science and Game Theory Data Structures and Algorithms We consider discrete allocation problem where $m$ indivisible goods are to be divided among $n$ agents. When agents' valuations are additive, the well-known cycle cancelling lemma by Lenstra, Shmoys, and Tardos plays a key role in design and analysis of rounding algorithms. In this paper, we prove an analogous lemma for the case of submodular valuations. Our algorithm removes cycles in the support graph of a fractional allocation while guaranteeing that each agent's value, measured using the multilinear extension, does not decrease. We demonstrate applications of the cycle-canceling algorithm, along with other ideas, to obtain new algorithms and results for three well-studied allocation objectives: max-min (Santa Claus problem), Nash social welfare (NSW), and maximin-share (MMS). For the submodular NSW problem, we obtain a $\frac{1}{5}$-approximation; for the MMS problem, we obtain a $\frac{1}{2}(1-1/e)$-approximation through new simple algorithms. For various special cases where the goods are "small" valued or the number of agents is constant, we obtain tight/best-known approximation algorithms. All our results are in the value-oracle model. |
| title | Cycle Cancellation for Submodular Fractional Allocations and Applications |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.21099 |