BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1169
DTSTAMP:20230914T125953Z
SUMMARY:Finding a satisfactory permutation
DESCRIPTION:Speaker: Kshitij Gajjar (National University of Singapore)\n\nA
bstract: \nYou have n candidates to fill up n vacant positions in an offic
e. The question is which candidate gets which position? To decide this\, y
ou ask non-candidates to vote. There are n! ways to allocate the positions
\, each corresponding to a permutation over [n]. Different voters may come
up with different permutations\, and your task is to find a permutation t
hat satisfies all the voters (or minimizes their dissatisfaction).\nThis p
roblem has several applications\, namely in computational biology\, DNA st
orage systems\, speech recognition\, social choice theory\, and classifica
tion. Surprisingly\, no poly(n)-time algorithm is known for this problem\,
even when there are only 4 voters. In this talk\, I will present a 1.5-ap
proximation algorithm for this problem\, whose runtime is poly(n) time whe
n the number of voters is a constant. This is joint work with Diptarka Cha
kraborty (NUS) and Agastya Vibhuti Jha (EPFL).\n\nZoom link: https://zoom.
us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09\n
URL:https://www.tcs.tifr.res.in/web/events/1169
DTSTART;TZID=Asia/Kolkata:20211105T171500
DTEND;TZID=Asia/Kolkata:20211105T181500
END:VEVENT
END:VCALENDAR