• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
028.pdf (681.4Kb)
Type
Communication / Conférence
Date
2016
Conference title
Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016
Conference date
2016-07
Conference city
New York
Conference country
United States
Book title
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July
Book author
Kambhampati, Subbarao
Publisher
AAAI Press / IJCAI
ISBN
978-1-57735-770-4
Pages
144--150
Metadata
Show full item record
Author(s)
Caragiannis, Ioannis
Computer 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 cc
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; Optimization

Related items

Showing items related by title and author.

  • Thumbnail
    Conference Program Design with Single-Peaked and Single-Crossing Preferences 
    Fotakis, Dimitris; Gourvès, Laurent; Monnot, Jérôme (2016) Communication / Conférence
  • Thumbnail
    Possible Winners in Approval Voting 
    Barrot, Nathanaël; Gourvès, Laurent; Lang, Jérôme; Monnot, Jérôme (2013) Communication / Conférence
  • Thumbnail
    On maximin share allocations in matroids 
    Gourvès, Laurent; Monnot, Jérôme (2019) Article accepté pour publication ou publié
  • Thumbnail
    Complexity of trails, paths and circuits in arc-colored digraphs 
    Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2013) Article accepté pour publication ou publié
  • Thumbnail
    On paths, trails and closed trails in edge-colored graphs 
    Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2012) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo