Jochen Koenemann, Kanstantsin Pashkovich and Natig Tofigzade were announced the recipients of the SAGT 2020 Best Paper Award for their paper "Approximating Stable Matchings with Ties of Bounded Size".
The abstract of the paper reads: "Finding a stable matching is one of the central problems in algorithmic game theory. If participants are allowed to have ties and incomplete preferences, computing a stable matching of maximum cardinality is known to be NP-hard. In this paper we present a (3L−2)/(2L−1)-approximation algorithm for the stable matching problem with ties of size at most L and incomplete lists. Our result matches the known lower bound on the integrality gap for the associated LP formulation."
The results in the paper form the basis for Natig's recently completed Master's thesis entitled "An Algorithm for Stable Matching with Approximation up to the Integrality Gap".
