• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • 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

Les matroïdes et leur implication dans l'allocation de ressources indivisibles : algorithmes d'approximation avec garantie de performance

Matroids and their implication in the allocation of indivisible resources : approximation algorithms with guaranteed performance

Tlilane, Lydia (2014), Les matroïdes et leur implication dans l'allocation de ressources indivisibles : algorithmes d'approximation avec garantie de performance, doctoral thesis prepared under the supervision of Monnot, Jérôme, Université Paris Dauphine, 216 p.

View/Open
2014PA090068.pdf (1.481Mb)
Type
Thèse
Date
2014-11
Pages
216
Metadata
Show full item record
Author(s)
Tlilane, Lydia
Under the direction of
Monnot, Jérôme
Abstract (FR)
Nous nous intéressons dans cette thèse à la problématique de la décision collective. L’objectif est de déterminer une solution de compromis pour des problèmes soumis à de multiples points de vue. Les problèmes considérés sont de nature combinatoire. Plus précisément, il s’agit de la classe des systèmes d’ensembles qui ont une structure de matroïde. La théorie des matroïdes est centrale en optimisation combinatoire, elle a permis d’unifier des structures apparemment séparées comme les arbres et les couplages dans les graphes et elle a engendré des algorithmes efficaces pour résoudre des problèmes d’optimisation non triviaux en temps polynomial. Nous nous intéressons à fournir des algorithmes d’approximation polynomiaux centralisés et décentralisés avec garantie de performance pour déterminer une solution de compromis qui est une base du matroïde. La solution de compromis doit également être équitable pour tous les membres de la collectivité. Nous portons un intérêt particulier au problème de partage équitable de biens indivisibles qui est une thématique importante en choix social computationnel et dont le problème se modélise par les matroïdes.
Abstract (EN)
In this thesis, we are interested in collective decision-making. The objective is to find a tradeoff solution for problems that are evaluated by multiple points of view. We consider problems having a matroid structure. Matroid theory is significant in combinatorial optimization, it helped to unify apparently separated structures like forests and matchings in graphs and it includes efficient algorithms for solving non-trivial optimization problems in polynomial time. We are interested to provide polynomial time centralized and decentralized approximation algorithms for finding a tradeoff solution which is a base of the matroid. The tradeoff solution must also be fair for all the members of the community. We are particularly interested in the issue of the fair division of indivisible goods which is central in computational social choice and that can be modeled by matroids.
Subjects / Keywords
Optimisation combinatoire; Approximation polynomiale à garantie de performance; Matroïdes; Allocation de biens indivisibles; Notions d’équité; Combinatorial optimization; Polynomial time approximation with guaranteed performance; Matroids; Allocation of indivisible goods; Fairness notions
JEL
C44 - Operations Research; Statistical Decision Theory

Related items

Showing items related by title and author.

  • Thumbnail
    Worst case compromises in matroids with applications to the allocation of indivisible goods 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2015) Article accepté pour publication ou publié
  • Thumbnail
    A matroid approach to the worst case allocation of indivisible goods 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
  • Thumbnail
    Approximation du point idéal dans des matroïdes: bornes et algorithmes 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
  • Thumbnail
    A parameterized approximation for matroids with multiple objectives 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
  • Thumbnail
    A guaranteed robust solution on a matroid 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
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