Bin Packing and Covering: Pushing the Frontier on the Maximin Share Fairness
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_ | 1866916990954766336 |
|---|---|
| author | Li, Bo Sun, Ankang Wang, Zunyu Zhou, Yu |
| author_facet | Li, Bo Sun, Ankang Wang, Zunyu Zhou, Yu |
| contents | We study a fundamental fair allocation problem, where the agent's value is determined by the number of bins either used to pack or cover the items allocated to them. Fairness is evaluated using the maximin share (MMS) criterion. This problem is not only motivated by practical applications, but also serves as a natural framework for studying group fairness. As MMS is not always satisfiable, we consider two types of approximations: cardinal and ordinal. For cardinal approximation, we relax the requirements of being packed or covered for a bin, and for ordinal approximation, we relax the number of bins that are packed or covered. For all models of interest, we provide constant approximation algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_04425 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bin Packing and Covering: Pushing the Frontier on the Maximin Share Fairness Li, Bo Sun, Ankang Wang, Zunyu Zhou, Yu Computer Science and Game Theory We study a fundamental fair allocation problem, where the agent's value is determined by the number of bins either used to pack or cover the items allocated to them. Fairness is evaluated using the maximin share (MMS) criterion. This problem is not only motivated by practical applications, but also serves as a natural framework for studying group fairness. As MMS is not always satisfiable, we consider two types of approximations: cardinal and ordinal. For cardinal approximation, we relax the requirements of being packed or covered for a bin, and for ordinal approximation, we relax the number of bins that are packed or covered. For all models of interest, we provide constant approximation algorithms. |
| title | Bin Packing and Covering: Pushing the Frontier on the Maximin Share Fairness |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2510.04425 |