Proportionally Fair Makespan Approximation
Authors: Michal Feldman, Jugal Garg, Vishnu V. Narayan, Tomasz Ponitka
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result demonstrates that there exists a proportional mechanism (with payments) that achieves a 3/2-approximation to the optimal makespan, and this ratio is tight. To prove this result, we provide a full characterization of allocation functions that can be made proportional with payments. Furthermore, we show that for instances with normalized costs, there exists a proportional mechanism that achieves the optimal makespan. |
| Researcher Affiliation | Collaboration | Michal Feldman1,2, Jugal Garg3, Vishnu V. Narayan1, Tomasz Ponitka1 1Tel Aviv University 2Microsoft ILDC 3University of Illinois at Urbana Champaign, USA |
| Pseudocode | Yes | Algorithm 1: Anti-Diagonal Mechanism |
| Open Source Code | No | The information is insufficient. The paper does not explicitly state that source code is provided or give a link to a code repository. |
| Open Datasets | No | The information is insufficient. The paper discusses theoretical models and problem instances (e.g., 'm-by-n matrix c', 'general instances C', 'normalized instances N') rather than empirical datasets used in experiments. |
| Dataset Splits | No | The information is insufficient. The paper is theoretical and does not use empirical datasets, therefore, no dataset splits are discussed. |
| Hardware Specification | No | The information is insufficient. The paper is theoretical and does not describe any experimental setup or specific hardware used for computations. |
| Software Dependencies | No | The information is insufficient. The paper is theoretical and does not specify any software dependencies or versions. |
| Experiment Setup | No | The information is insufficient. The paper is theoretical and focuses on mathematical proofs and mechanism design, not empirical experimentation with specific setup details like hyperparameters. |