BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T013805Z
UID:Seminar-dept-419@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20161004T130000
DTEND:20161004T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr Chien-Chung Huang: Minimizing the number of unhappy singles: improved approximation algorithms for the stable marriage problem\n\nWe consider the problem of computing a large stable matching\n\nin a bipartite graph G = (A\cup B, E) where each vertex u \in A\cup B\n\nranks its neighbors in an order of preference, perhaps involving ties.\n\n\n\nA matching M is said to be stable  if there is no edge (a,b) such that a\n\nis unmatched or prefers b to M(a) and similarly,\n\nb is unmatched or prefers a to M(b). While a stable matching in G can be\n\neasily computed in linear time by the Gale-Shapley algorithm,\n\nit is known that computing a maximum size stable matching is APX-hard.\n\nIn this talk, we report the latest results (for both upper and lower\n\nbounds in approximability) on this problem.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=419
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR