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