Venerdì 5 marzo 2021 alle ore 15:00, il dott. Chien-Chung Huang (CNRS / École Normale Supérieure PSL, Paris) presenterà il seminario di Logica e Informatica Teorica dal titolo: "Minimizing the Number of Unhappy Singles: Improved Approximation Algorithms for Stable Marriage".

Abstract:
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: https://bit.ly/3uPLhvf.