Optimal Capacity Modification for Stable Matchings with Ties
Authors: Keshav Ranjan, Meghana Nasre, Prajakta Nimbhorkar
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We explore two natural optimization criteria: (i) minimizing the total capacity increase across all hospitals (MINSUM) and (ii) minimizing the maximum capacity increase for any hospital (MINMAX). We show that the MINSUM problem admits a polynomial-time algorithm, whereas the MINMAX problem is NP-hard. We prove an analogue of the Rural Hospitals theorem for the MINSUM problem. When each hospital incurs a cost for a unit increase in its quota, the MINSUM problem becomes NP-hard, even for 0/1 costs. In fact, we show that the problem cannot be approximated to any multiplicative factor. We also present a polynomial-time algorithm for optimal MINSUM augmentation when a specified subset of edges is required to be included in the matching. |
| Researcher Affiliation | Academia | 1IIT Madras 2Chennai Mathematical Institute and UMI Re La X EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: Algorithm for MINSUM-SS |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code or links to code repositories. The reference to '[Ranjan et al., 2024]' is for a 'full version' on arXiv, which is a preprint server and not a code repository. |
| Open Datasets | No | The paper focuses on theoretical graph-theoretic problems (Hospitals/Residents problem with ties) and algorithm design. It describes problem instances abstractly (e.g., 'bipartite graph G = (R H, E)') rather than utilizing or referencing any specific publicly available datasets for empirical evaluation. |
| Dataset Splits | No | The paper focuses on theoretical problem analysis and algorithm design for matching problems. It does not involve empirical experiments with datasets that would require train/test/validation splits. |
| Hardware Specification | No | The paper focuses on theoretical results, including proofs of polynomial-time solvability and NP-hardness for optimization problems. It does not describe any computational experiments that would require hardware specifications. |
| Software Dependencies | No | The paper presents theoretical algorithms and complexity analysis. There are no mentions of specific software, libraries, or their version numbers used for any experimental or computational tasks. |
| Experiment Setup | No | The paper describes theoretical algorithms and complexity results. It does not involve empirical experiments, and therefore, does not provide details such as hyperparameters, training configurations, or other system-level settings. |