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://teams.microsoft.com/dl/launcher/launcher.html?url=%2F_%23%2Fl%2Fmeetup-join%2F19%3A388bb369590943489346c5edc8bb7b83%40thread.tacv2%2F1613998813762%3Fcontext%3D%257b%2522Tid%2522%253a%2522ffb4df68-f464-458c-a546-00fb3af66f6a%2522%252c%2522Oid%2522%253a%25220403197b-0405-4fee-b33b-ddfb43c6b8a1%2522%257d%26anon%3Dtrue&type=meetup-join&deeplinkId=aae237d9-b664-4809-80a5-d29fd3233e67&directDl=true&msLaunch=true&enableMobilePage=true&suppressPrompt=true
org: BONIFACI Vincenzo