BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/218
DTSTAMP:20230914T125915Z
SUMMARY:Near-Popular Matchings in the Roommates Problem
DESCRIPTION:Speaker: Chien-Chung Huang\nHumboldt-UniversitÃ¤\;t zu\n
Berlin Institut fÃ¼\;r Informatik 10099\nBerlin Germany\n\nAbstract
: \nOur input is a graph $G = (V\, E)$ where each vertex ranks its neighbo
rs in a strict order of preference. The problem is to compute a matching i
n $G$ that captures the preferences of the vertices in a popular way. Matc
hing $M$ is more popular than matching $M'$ if the number of vertices that
prefer $M$ to $M'$ is more than those that prefer $M'$ to $M$. The unpopu
larity factor of $M$ measures by what factor any matching can be more popu
lar than $M$. We show that $G$ always admits a matching whose unpopularity
factor is $O(\\log|V|)$\, and such a matching can be computed in linear t
ime. In our problem the optimal matching would be a least unpopularity fac
tor matching. We will show that computing such a matching is NP-hard. In f
act\, for any $\\epsilon$\, it is NP-hard to compute a matching whose unpo
pularity factor is at most $4/3 - \\epsilon$ of the optimal.\n
URL:https://www.tcs.tifr.res.in/web/events/218
DTSTART;VALUE=DATE:20110926
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR