Locally Fair Partitioning
Authors: Pankaj K. Agarwal, Shao-Heng Ko, Kamesh Munagala, Erin Taylor4752-4759
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper focuses on a restricted case when points lie in 1D. The problem is non-trivial even in this case. We consider both adversarial and beyond worst-case settings for this problem. For the former, we characterize the input parameters for which a locally fair partition always exists; we also show that a locally fair partition may not exist for certain parameters. We then consider input models where there are runs of red and blue points. For such clustered inputs, we show that a locally fair partition may not exist for certain values of σ, but an approximate locally fair partition exists if we allow some regions to have smaller sizes. We finally present a polynomial-time algorithm for computing a locally fair partition if one exists. |
| Researcher Affiliation | Academia | Pankaj K. Agarwal, Shao-Heng Ko, Kamesh Munagala, Erin Taylor Department of Computer Science, Duke University {pankaj, sk684, kamesh, ect15}@cs.duke.edu |
| Pseudocode | No | The paper describes a dynamic programming algorithm but does not provide structured pseudocode blocks or a clearly labeled algorithm figure. |
| Open Source Code | No | The paper provides a link to an arXiv pre-print for the full version (https://arxiv.org/abs/2112.06899), but it does not state that source code for the described methodology is available or provide a link to a code repository. |
| Open Datasets | No | The paper discusses 'input instances' of points but does not use or refer to any publicly available or open datasets with specific access information (e.g., URL, DOI, citation to an established dataset). |
| Dataset Splits | No | The paper is theoretical and does not describe experimental data or the use of training, validation, or test splits for model evaluation. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and analysis. It does not mention any specific hardware used for computations or experiments. |
| Software Dependencies | No | The paper is theoretical and describes an algorithm. It does not list any specific software dependencies or versions required for implementation or execution. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design. It does not describe an experimental setup with hyperparameters, training configurations, or other system-level settings. |