Minimizing the number of unhappy singles
Time: 11:00 -- Location: LIX
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.