Afficher la notice abrégée

dc.contributor.authorCaragiannis, Ioannis
dc.contributor.authorGourvès, Laurent
dc.contributor.authorMonnot, Jérôme
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.person.labIds89996
hal.person.labIds989
hal.person.labIds989
hal.identifierhal-01371003*


Fichiers attachés à cette notice

Thumbnail

Ce document fait partie de la (des) collection(s) suivante(s)

Afficher la notice abrégée