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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
On the PTAS for Maximin Shares in an Indivisible Mixed Manna
Authors: Rucha Kulkarni, Ruta Mehta, Setareh Taki5523-5530
AAAI 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we complement the hardness result by obtaining a PTAS to compute the MMS value, when its absolute value is at least 1/p times either the total value of all the goods or total cost of all the chores, for some constant p valued at least 1. The algorithm runs in time O(mn L), where m,n are the number of items and agents, and L is the bit-length of the input. One of the key tools used by our algorithm is a carefully designed Integer Program (IP) that can be solved in polynomial-time. |
| Researcher Affiliation | Academia | 1 University of Illinois at Urbana-Champaign EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: Algorithm for GC-MMS |
| Open Source Code | No | The paper does not contain any statement about open-sourcing their code or providing a link to a repository. |
| Open Datasets | No | The paper is theoretical, focusing on algorithmic design and proofs, and does not involve empirical training on datasets. It defines an abstract 'MMS instance' but does not use empirical data. |
| Dataset Splits | No | The paper is theoretical and does not describe any experimental setup involving training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and describes algorithms and proofs; it does not specify any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and discusses algorithms (e.g., 'Lenstra’s algorithm') but does not specify software dependencies with version numbers needed for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and describes algorithms and proofs; it does not provide details on an experimental setup with hyperparameters or system-level training settings. |