Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Improved Maximin Share Approximations for Chores by Bin Packing
Authors: Jugal Garg, Xin Huang, Erel Segal-Halevi
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show the existence of 1-out-of-9/11n MMS allocations, which improves the state-of-the-art factor of 1-out-of-3/4n. 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. |
| Researcher Affiliation | Academia | Jugal Garg1, Xin Huang2, Erel Segal-Halevi3 1University of Illinois at Urbana Champaign, USA 2Kyushu University, Fukuoka, Japan 3Ariel University, Ariel 40700, Israel EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: Reduction by swapping for a factored cost function... Algorithm 2: Reduction by swapping for a bivalued cost function |
| Open Source Code | No | The paper does not provide any specific links to source code repositories or explicit statements about code availability for the described methodology. |
| Open Datasets | No | The paper focuses on theoretical analysis of chore allocation algorithms and does not use or refer to any specific publicly available datasets for experimental evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation on datasets, thus no dataset splits are mentioned. |
| Hardware Specification | No | The paper focuses on theoretical proofs and algorithm design, not experimental evaluation, and therefore does not specify any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithmic design and analysis, without detailing any software dependencies or versions for implementation or experimentation. |
| Experiment Setup | No | The paper presents theoretical results and algorithms rather than empirical experiments, so it does not contain details about experimental setup or hyperparameters. |