Seminari del Dipartimento


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.

Per partecipare al Seminario cliccare sul seguente Link:
org: BONIFACI Vincenzo

Copyright© 2014 Dipartimento di Matematica e Fisica