Aller au menu Aller au contenu
Optimisation Combinatoire
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Optimisation Combinatoire
Optimisation Combinatoire

> GSCOP_Recherche > GSCOP_OptimisationCombinatoire

Séminaire de Mathématiques Discrètes le 20 mars à 11h - Nicolas Bousquet

Publié le 16 mars 2015
A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo
Colloque / Séminaire 20 mars 2015

Vendredi prochain, le 20 mars à 11h, en salle C219, nous aurons exceptionnellement un séminaire de Nicolas Bousquet (Université McGill, Montréal). Nicolas candidate au CNRS dans notre équipe cette année.

vignette-seminaireoc.jpg

vignette-seminaireoc.jpg

 

Coalition games on interaction graphs

 



We consider cooperative games where the viability of a coalition is determined by whether or not its members have the ability to communicate amongst themselves. This necessary condition for viability was proposed by Myerson and is modeled via an interaction graph; a coalition S of vertices is then viable if and only if the graph induced graph S is connected.

The non-emptiness of the core of a coalition game can be tested by a well-known covering LP. Moreover, the integrality gap of its dual packing LP defines exactly the multiplicative least-core and the relative cost of stability of the coalition game. This gap is upper bounded by the packing-covering ratio which is known to be at most the treewidth of the interaction graph plus one.

We examine the packing-covering ratio and integrality gaps of graphical coalition games in more detail. First we introduce a new graph parameter, called the vinewidth (a parameter derived from the treewidth), which characterizes the worst packing-covering ratio. Then we will show that this new parameter correctly evaluates both primal and dual integrality gaps.

Joint work with Zhentao Li and Adrian Vetta.

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo

mise à jour le 23 mars 2015

  • Tutelle CNRS
  • Tutelle Grenoble INP
  • Université Joseph Fourier
  • Tutelle UMR
Univ. Grenoble Alpes