Mendeley出力
＜会議発表論文＞
Improved Maximin Share Approximations for Chores by Bin Packing
| 作成者 | |
|---|---|
| 本文言語 | |
| 出版者 | |
| 発行日 | |
| 収録物名 | |
| 巻 | |
| 号 | |
| 開始ページ | |
| 終了ページ | |
| 会議情報 | |
| アクセス権 | |
| 権利関係 | |
| 関連DOI | |
| 関連DOI | |
| 関連URI | |
| 関連HDL | |
| 関連ISBN | |
| 関連HDL | |
| 関連情報 | |
| 概要 | We study fair division of indivisible chores among n agents with additive cost functions using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist for more th...an two agents, the goal has been to improve its approximations and identify interesting special cases where MMS allocations exist. We show the existence of · 1-out-of-⌊(9n)/(11)⌋ MMS allocations, which improves the state-of-the-art factor of 1-out-of-⌊(3n)/(4)⌋. · MMS allocations for factored instances, which resolves an open question posed by Ebadian et al. (2021). · 15/13-MMS allocations for personalized bivalued instances, improving the state-of-the-art factor of 13/11. We achieve these results by leveraging the HFFD algorithm of Huang and Lu (2021). Our approach also provides polynomial-time algorithms for computing an MMS allocation for factored instances and a 15/13-MMS allocation for personalized bivalued instances.続きを見る |
詳細
| PISSN | |
|---|---|
| EISSN | |
| レコードID | |
| 関連ISBN | |
| 注記 | |
| 助成情報 | |
| 登録日 | 2025.09.05 |
| 更新日 | 2025.09.08 |