2018/08/13 by Robert Chiang, Kanstantsin Pashkovich, Chiang, Robert +1
Computer Science · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems #Logic, Reasoning, and Knowledge #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.1808.04510
openalex publication_date 2018/08/13 · openalex created_date 2022/08/04 · openalex updated_date 2026/07/28
The stable matching problem is one of the central problems of algorithmic\ngame theory. If participants are allowed to have ties, the problem of finding a\nstable matching of maximum cardinality is an NP-hard problem, even when the\nties are of size two. Moreover, in this setting it is UGC-hard to provide an\napproximation for the maximum cardinality stable matching problem with a\nconstant factor smaller than 4/3. In this paper, we give a tight analysis of an\napproximation algorithm given by Huang and Kavitha for the maximum cardinality\nstable matching problem with ties of size two, demonstrating an improved\n4/3-approximation factor.\n