You have n candidates to fill up n vacant positions in an office. The question is which candidate gets which position? To decide this, you 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 that satisfies all the voters (or minimizes their dissatisfaction).
This problem has several applications, namely in computational biology, DNA storage systems, speech recognition, social choice theory, and classification. 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-approximation algorithm for this problem, whose runtime is poly(n) time when the number of voters is a constant. This is joint work with Diptarka Chakraborty (NUS) and Agastya Vibhuti Jha (EPFL).
