On the PTAS for Maximin Shares in an Indivisible Mixed Manna
Authors: Rucha Kulkarni, Ruta Mehta, Setareh Taki5523-5530
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | 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 ruchark2@illinois.edu, rutameht@illinois.edu, staki2@illinois.edu |
| 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. |