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 [Formula: see text]-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 [Formula: see text]-stabilities, which mean that for an edge to block, the improvement should be at least [Formula: see text]. 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 [Formula: see text]-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. History: This paper has been accepted for the Mathematics of Operations Research special issue on Market Design. Funding: 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].