BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/500
DTSTAMP:20230914T125927Z
SUMMARY:Minimizing the Number of Unhappy Singles: An Improved Approximation
Algorithm for the Stable Marriage Problem With One-sided Ties
DESCRIPTION:Speaker: Chien-Chung Huang (Chalmers University\nDepartment of
Computer Science and Engineering\nGothenburg\nSweden)\n\nAbstract: \nAbstr
act: We consider the problem of computing a large stable matching in a bip
artite graph G = (A U B\, E) where each vertex ranks its neighbors in an o
rder of preference\, perhaps involving ties.The goal is to compute a large
stable matching. It is known that computing a maximum size stable matchin
g is APX-hard. We present an improved approximation algorithm for the case
when ties are present only in the preference lists of vertices in B. This
case is also APX-hard and the current best approximation ratio known here
is 25/17\, we show a simple linear time algorithm that achieves an approx
imation ratio of 22/15.\n
URL:https://www.tcs.tifr.res.in/web/events/500
DTSTART;TZID=Asia/Kolkata:20140613T113000
DTEND;TZID=Asia/Kolkata:20140613T123000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR