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