A Simple 1.5-Approximation Algorithm for a Wide Range of Maximum-Size Stable Matching Problems

• 成果类型: Article; Early Access
• 署名作者: Csaji, Gergely; Kiraly, Tamas; Yokoi, Yu
• 署名单位: Eotvos Lorand University; Institute of Science Tokyo
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0725
• 发表日期: 2025
• 关键词: stability

摘要

This paper considers the problem of finding maximum-size stable matchings in the presence of ties, a well-known NP-hard problem, by extending the existing 32-approximation algorithm to a common generalization of many previously studied and newly introduced models. These include the existence of critical agents, where matching as many of these agents as possible is prioritized; free edges that cannot be blocking edges; and triangle-stabilities, which mean that for an edge to block, the improvement should be at least triangle. We also introduce notions to generalize these further by introducing edge-specific thresholds for each agent, which allow the blocking condition to vary based on the agents and edges, so our framework has a wide range of existing and potential applications. We show that the edge-duplicating technique allows us to treat these different types of generalizations simultaneously while also making the algorithm, proofs, and analysis much simpler and shorter than in previous approaches. In particular, we answer an open question about the existence of a 32-approximation algorithm for the Max-SMTI problem with free edges. This demonstrates that our technique successfully exploits a fundamental feature of these problems and has the potential to be useful in many future applications.