Maximum weakly stable matchings in graphs without odd preference cycles

From Egres Open
Jump to: navigation, search

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]. 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 [2] 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).

References

  1. 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.
  2. R. W. Irving, D. F. Manlove, The stable roommates problem with ties, Journal of Algorithms 43 (2002), 85-105. DOI link. Author link.