Events by date

Title: On the approximability of the maximum cardinality stable matching problem with ties  

Speaker: Kanstantsin Pashkovich Affliliation: University of Waterloo Zoom: Contact Emma Watson

Abstract:

The maximum cardinality stable matching problem is central in game theory. When participants are allowed to have ties in their preferences, the problem of finding a stable matching of maximum cardinality is NP-hard, 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.