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..
Proportionally Fair Makespan Approximation
Authors: Michal Feldman, Jugal Garg, Vishnu V. Narayan, Tomasz Ponitka
AAAI 2025 | Venue PDF | 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. |