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..
A Little Charity Guarantees Fair Connected Graph Partitioning
Authors: Ioannis Caragiannis, Evi Micha, Nisarg Shah4908-4916
AAAI 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove a lower bound which shows that α-balancedness and α-proportionality cannot be guaranteed for any α < 2 and α < 2 1/n, respectively (Theorem 1). Next, for n {2, 3}, we show that this bound is tight and such partitions can be found in polynomial time (Theorems 2 and 3). For higher values of n, we provide three efficient algorithms which obtain generally incomparable approximation guarantees: one ensures (3 + O(n/m))-balancedness and 3-proportionality, another ensures 4-balancedness and 2-proportionality, and the final one ensures (2+O(n2/m))balancedness and (2 1/n + O(n2/m))-proportionality. |
| Researcher Affiliation | Academia | Ioannis Caragiannis,1 Evi Micha,2 Nisarg Shah2 1 Aarhus University 2University of Toronto |
| Pseudocode | Yes | Algorithm 1: 2-balancedness and 1.5-proportionality for n = 2... Algorithm 2: (3 + O(n/m))-balancedness and 3proportionality for n 2... Algorithm 3: 4-balancedness and 2-proportionality for n 2 |
| Open Source Code | No | The paper does not provide any concrete access to source code, such as repository links or explicit statements about code availability. |
| Open Datasets | No | This paper is theoretical and does not use datasets. Therefore, it does not provide information about public dataset access for training. |
| Dataset Splits | No | This paper is theoretical and does not use datasets. Therefore, it does not provide information about dataset splits for validation. |
| Hardware Specification | No | This is a theoretical paper that does not involve running experiments on specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | This is a theoretical paper that does not involve empirical experiments requiring specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with hyperparameters or system-level training settings. |