Show simple item record

hal.structure.identifierComputer Technology Institute [CTI]
dc.contributor.authorCaragiannis, Ioannis
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGourvès, Laurent
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2016-09-23T14:26:25Z
dc.date.available2016-09-23T14:26:25Z
dc.date.issued2016
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15827
dc.language.isoenen
dc.subjectComputational Complexityen
dc.subjectApproximation algorithmsen
dc.subjectOptimizationen
dc.subject.ddc003en
dc.titleAchieving Proportional Representation in Conference Programsen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.en
dc.identifier.citationpages144--150en
dc.relation.ispartoftitleProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 Julyen
dc.relation.ispartofeditorKambhampati, Subbarao
dc.relation.ispartofpublnameAAAI Press / IJCAIen
dc.relation.ispartofdate2016
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-1-57735-770-4en
dc.relation.conftitleTwenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016en
dc.relation.confdate2016-07
dc.relation.confcityNew Yorken
dc.relation.confcountryUnited Statesen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2016-09-23T14:07:19Z
hal.identifierhal-01371003*
hal.version1*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record