Logica e Informatica Teorica Minimizing the Number of Unhappy Singles: Improved Approximation Algorithms for Stable Marriage Chien-Chung Huang 05-03-2021 - 15:00 modalità telematica (telematic form)
We consider the problem of computing a large stable matching in a bipartite graph G = (A ∪ B, E) where each vertex u ∈ A ∪ B ranks its neighbors in an order of preference, perhaps involving ties. Let the matched partner of u in a matching M be M(u). 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. We design an algorithm to give a 1.4667-approximation for the special case where all ties of the preferences appear on the B-side. This algorithm is purely combinatorial and takes only linear time. |