ML Anthology

Achieving Proportional Representation in Conference Programs

Ioannis Caragiannis, Laurent Gourvès, Jérôme Monnot
IJCAI 2016 pp. 144-150
/ijcai/2016/caragiannis2016ijcai-achieving/

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. PDF

PDF IJCAI Semantic Scholar

Cite

Text

Caragiannis et al. "Achieving Proportional Representation in Conference Programs." International Joint Conference on Artificial Intelligence, 2016.

Markdown

[Caragiannis et al. "Achieving Proportional Representation in Conference Programs." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/caragiannis2016ijcai-achieving/)

BibTeX

@inproceedings{caragiannis2016ijcai-achieving,
  title     = {{Achieving Proportional Representation in Conference Programs}},
  author    = {Caragiannis, Ioannis and Gourvès, Laurent and Monnot, Jérôme},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {144-150},
  url       = {https://mlanthology.org/ijcai/2016/caragiannis2016ijcai-achieving/}
}