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

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 Δ-stabilities, which mean that for an edge to block, the improvement should be at least Δ. 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.<bold>History:</bold> This paper has been accepted for the <italic>Mathematics of Operations Research</italic> special issue on Market Design.<bold>Funding:</bold> G. Csáji was supported by the Hungarian Scientific Research Fund (OTKA) [Grant K143858], the Momentum Grant of Magyar Tudományos Akadémia (the Hungarian Academy of Sciences) [Grant 2021-2/2021], and the Ministry of Culture and Innovation of Hungary from the National Research, Development and Innovation fund, financed under the KDP-2023 funding scheme [Grant C2258525]. T. Király is supported by the Lendület Programme of the Hungarian Academy of Sciences [Grant LP2021-1/2021] and the Ministry of Innovation and Technology of Hungary from the National Research, Development and Innovation Fund [Grants ELTE TKP 2021-NKTA-62 and K143858]. Y. Yokoi is supported by Japan Science and Technology Agency [JST PRESTO Grant JPMJPR212B, JST ERATO Grant JPMJER2301, and JST CRONOS Japan Grant JPMJCS24K2]. [ABSTRACT FROM AUTHOR]

Copyright of Mathematics of Operations Research is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)