Achieving Proportional Representation in Conference Programs / 144
Ioannis Caragiannis, Laurent Gourvès, Jérôme Monnot

We study the optimization problem of designing the program of a conference with parallel sessions, so that the intended participants are as happy as possible from the talks they can attend. Interestingly, this can be thought of as a two-dimensional extension of a scheme proposed by Chamberlin and Courant [1983] for achieving proportional representation in multi-winner elections. We show that different variations of the problem are computationally hard by exploiting relations of the problem with well-known hard graph problems. On the positive side, we present polynomial-time algorithms that compute conference programs that have a social utility that is provably close to the optimal one (within constant factors). Our algorithms are either combinatorial or based on linear programming and randomized rounding.

PDF