What's on in Computing Science?

Date: Tuesday, 21 February, 2012
Time: 16:00
Location: Sir Alwyn Williams Building, 422 Seminar Room
[FATA talk] “Almost stable” matchings in the Roommates problem
David Manlove
An instance of the classical Stable Roommates problem need not admit a stable matching. This motivates the problem of finding a matching that is “as stable as possible”, i.e., admits the minimum number of blocking pairs. It is known that this problem is NP-hard and difficult to approximate. We extend the study to the Stable Roommates problem with Incomplete lists. In particular, we consider the case that the lengths of the lists are bounded by some integer d. We give a lower bound for the approximability of the problem of finding a matching with the minimum number of blocking pairs that holds even if d = 3. However on the positive side we describe an approximation algorithm with performance guarantee (2d-3) for the problem when d>=3.
This is joint work with Peter Biro (Institute of Economics, Hungarian Academy of Sciences) and Eric McDermid (21st Century Technologies, inc), both formerly of this parish.

Contact: Dr Oana Andrei (oana.andrei@glasgow.ac.uk)

Add to my calendar