Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP
Authors: Jiehua Chen, Robert Ganian, Thekla Hamm
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate the following many-to-one stable matching problem with diversity constraints (SMTI-DIVERSE)... SMTI-DIVERSE is known to be NP-hard. However, as opposed to the NP-membership claims in the literature [Aziz et al., 2019; Huang, 2010], we prove that it is beyond NP: it is complete for the complexity class ΣP 2. In addition, we provide a comprehensive analysis of the problem s complexity from the viewpoint of natural restrictions to inputs and obtain new algorithms for the problem. |
| Researcher Affiliation | Academia | Jiehua Chen , Robert Ganian and Thekla Hamm TU Wien, Vienna, Austria jiehua.chen@tuwien.ac.at, rganian@gmail.com, thamm@ac.tuwien.ac.at |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. It provides proof sketches and theoretical analysis. |
| Open Source Code | No | The paper does not include any statement about releasing source code or provide a link to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on complexity analysis and algorithm design without empirical evaluation on specific datasets. Therefore, it does not mention dataset availability. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits. Thus, no training/validation/test splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments that would require specific software dependencies with version numbers. No such details are provided. |
| Experiment Setup | No | The paper is theoretical and focuses on complexity analysis and algorithm design. It does not describe an experimental setup with hyperparameters or system-level training settings. |