A Little Charity Guarantees Fair Connected Graph Partitioning
Authors: Ioannis Caragiannis, Evi Micha, Nisarg Shah4908-4916
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | 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. |