Paper Info
Title
Achieving Proportional Representation in Conference Programs.
Abstract
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.
Year
Venue
Field
2016
IJCAI
Approximation algorithm,Graph,Computer science,Theoretical computer science,Proportional representation,Randomized rounding,Artificial intelligence,Linear programming,Optimization problem,Machine learning,Computational complexity theory
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
8
3
Name
Order
Citations
PageRank
Ioannis Caragiannis185976.85
Laurent Gourvès224130.97
Jérôme Monnot351255.74