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

> Recherche > Optimisation combinatoire

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 cet article Facebook Twitter Linked In
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.

 

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 cet article Facebook Twitter Linked In

mise à jour le 23 mars 2015

Université Grenoble Alpes