Approximating Stable Matchings with Ties of Bounded Size.
2020
Finding a stable matching is one of the central problems in algorithmic game theory. If participants are allowed to have ties and incomplete lists, 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 preferences. Our result matches the known lower bound on the integrality gap for the associated LP formulation.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
17
References
0
Citations
NaN
KQI