Show simple item record

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

dc.contributor.advisorMonnot, Jérôme
hal.structure.identifier
dc.contributor.authorTlilane, Lydia*
dc.creatorTlilane, Lydia
dc.creatorMonnot, Jérôme
dc.creatorGourvès, Laurent
dc.creatorTlilane, Lydia
dc.creatorMonnot, Jérôme
dc.creatorGourvès, Laurent
dc.creatorTlilane, Lydia
dc.creatorMonnot, Jérôme
dc.creatorGourvès, Laurent
dc.creatorTlilane, Lydia
dc.creatorMonnot, Jérôme
dc.creatorGourvès, Laurent
dc.date2014
dc.date2013
dc.date2013
dc.date2015
dc.date.accessioned2015-03-23T15:39:26Z
dc.date.available2015-03-23T15:39:26Z
dc.date.issued2014-11
dc.identifierhttp://basepub.dauphine.fr/theses/2014PA090068
dc.identifier
dc.identifierhttps://tel.archives-ouvertes.fr/tel-01134377
dc.identifierhttp://www.theses.fr/2014PA090068
dc.identifier2014PA090068
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/14807
dc.description.abstractfrNous 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.en
dc.languagefr
dc.languageen
dc.languagefr
dc.languageen
dc.languageen
dc.language.isofren
dc.publisher
dc.publisher
dc.publisher
dc.publisherElsevier
dc.subjectOptimisation combinatoireen
dc.subjectApproximation polynomiale à garantie de performanceen
dc.subjectMatroïdesen
dc.subjectAllocation de biens indivisiblesen
dc.subjectNotions d’équitéen
dc.subjectCombinatorial optimizationen
dc.subjectPolynomial time approximation with guaranteed performanceen
dc.subjectMatroidsen
dc.subjectAllocation of indivisible goodsen
dc.subjectFairness notionsen
dc.subject.ddc003en
dc.subject.classificationjelC44en
dc.titleLes matroïdes et leur implication dans l'allocation de ressources indivisibles : algorithmes d'approximation avec garantie de performancefr
dc.titleMatroids and their implication in the allocation of indivisible resources : approximation algorithms with guaranteed performanceen
dc.typeThèseen
dc.subject.classificationrameauOptimisation combinatoire
dc.subject.classificationrameauMatroïdes
dc.subject.classificationrameauApproximation polynomiale
dc.subject.classificationrameauÉquité
dc.subject.classificationrameauDécision de groupe
dc.subject.classificationrameauAllocation des ressources
dc.contributor.editoruniversityUniversité Paris Dauphine
dc.description.abstractenIn 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.en
dc.identifier.citationpages216en
dc.identifier.theseid2014PA090068en
dc.subject.ddclabelRecherche opérationnelleen
dc.rights.intranetnonen
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record