Maximum weakly stable matchings in graphs without odd preference cycles
Let (G,<) be a preference system with ties where in every odd cycle there is a node that prefers its clockwise neighbour to its other neighbour, and there is another node that prefers its anti-clockwise neighbour to its other neighbour. How well can we approximate the maximum size weakly stable matching?
Remarks
Clearly, the maximum stable marriage problem is a special case, for which the best known approximation ratio is 3/2 by McDermid [1] (see also [2] and [3]). On the other hand, the preference system is guaranteed to have a weakly stable matching since there are no odd preference cycles, and, as Irving and Manlove [4] showed, the size of the maximum weakly stable matching is at most twice the size of the minimum weakly stable matching, which immediately gives a 2-approximation algorithm (find a stable matching for an arbitrary break of ties).
The approximation ratio as a function of tie lengths is also interesting. For the maximum stable marriage problem, Koenemann, Pashkovich and Tofigzade [5] gave a (3L−2)/(2L−1)-approximation algorithm, where L is the longest tie in a preference list.
References
- ↑ E. McDermid, A 3/2-Approximation Algorithm for General Stable Marriage, Proc. ICALP2009, Lecture Notes in Computer Science 5555 (2009), 689-700. DOI link. Author link.
- ↑ Z. Király, Linear time local approximation algorithm for maximum stable marriage, Algorithms 6(3), 471–484 (2013). DOI link
- ↑ K. Paluch, Faster and simpler approximation of stable matchings, Algorithms 7(2), 189–202 (2014). DOI link
- ↑ R. W. Irving, D. F. Manlove, The stable roommates problem with ties, Journal of Algorithms 43 (2002), 85-105. DOI link. Author link.
- ↑ J. Koenemann, K. Pashkovich, N. Tofigzade, Approximating Stable Matchings with Ties of Bounded Size, International Symposium on Algorithmic Game Theory (2020), arXiv link
