Minimizing the number of unhappy singles: improved approximation algorithms for the stable marriage problem

4^th October 2016, 13:00 Ashton Lecture Theater
Dr Chien-Chung Huang
CNRS, École Normale Supérieure d'Ulm
Paris, France

Abstract

We consider the problem of computing a large stable matching
in a bipartite graph G = (A\cup B, E) where each vertex u \in A\cup B
ranks its neighbors in an order of preference, perhaps involving ties.

A matching M is said to be stable if there is no edge (a,b) such that a
is unmatched or prefers b to M(a) and similarly,
b is unmatched or prefers a to M(b). While a stable matching in G can be
easily computed in linear time by the Gale-Shapley algorithm,
it is known that computing a maximum size stable matching is APX-hard.
In this talk, we report the latest results (for both upper and lower
bounds in approximability) on this problem.