Tutte Colloquium - Kanstantsin Pashkovich

Title: On the approximability of the stable matching problem with ties of size two and one-sided ties

Abstract:

The stable matching problem is central for game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum cardinality is an NP-hard problem, even when the ties are of size two. Moreover, in this setting it is UGC-hard to provide an approximation for the maximum cardinality stable matching problem with a constant factor smaller than 4/3. We give a tight analysis of an approximation algorithm given by Huang and Kavitha for the maximum cardinality stable matching problem with ties of size two, demonstrating an improved 4/3-approximation factor. We also provide a tight analysis of an approximation algorithm by Huang and Kavitha for one-sided ties.

Joint work with Felix Bauckholt, Laura Sanita and Robert Chiang.