
Achieving Proportional Representation in Conference Programs
Caragiannis, Ioannis; Gourvès, Laurent; Monnot, Jérôme (2016), Achieving Proportional Representation in Conference Programs, in Kambhampati, Subbarao, Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July, AAAI Press / IJCAI, p. 144--150
View/ Open
Type
Communication / ConférenceDate
2016Conference title
Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016Conference date
2016-07Conference city
New YorkConference country
United StatesBook title
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 JulyBook author
Kambhampati, SubbaraoPublisher
AAAI Press / IJCAI
ISBN
978-1-57735-770-4
Pages
144--150
Metadata
Show full item recordAuthor(s)
Caragiannis, IoannisComputer Technology Institute [CTI]
Gourvès, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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.Subjects / Keywords
Computational Complexity; Approximation algorithms; OptimizationRelated items
Showing items related by title and author.
-
Fotakis, Dimitris; Gourvès, Laurent; Monnot, Jérôme (2016) Communication / Conférence
-
Barrot, Nathanaël; Gourvès, Laurent; Lang, Jérôme; Monnot, Jérôme (2013) Communication / Conférence
-
Gourvès, Laurent; Monnot, Jérôme (2019) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2013) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2012) Article accepté pour publication ou publié