Abstract (EN)

We study the optimization problem of designing theprogram 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 ex-tension 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 computa-ionally 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.