Groupe

GT

Les GT se tiennent chaque vendredi de 14h à 15h (d'ordinaire en salle 178, ils se sont dématérialisés jusqu'à nouvel ordre). Vous êtes invités à venir 10 minutes avant pour partager thé, café et gâteaux.

Pour vous inscrire à la liste de diffusion, il suffit d'envoyer un mail à sympa@diff.u-bordeaux.fr avec pour sujet "subscribe labri.go-gt Cookie Monster", où Cookie est remplacé par votre prénom et Monster par votre nom.

Voir l'agenda des GT: webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.html https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.html; pour l'ajouter au vôtre, webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.ics https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics ou bien flasher le QRCode suivant:

Prochains exposés :

Les exposés en ligne sont accessibles à cette adresse : https://webconf.u-bordeaux.fr/b/mar-ef4-zed.

Vendredi 15 décembre à 14h - Chien-Chung Huang
Matroid-Constrained Maximum Vertex Cover
We introduce the problem of Matroid-Constrained Vertex Cover: given a graph with weights on the edges and a matroid imposed on the vertices, our problem is to choose a subset of vertices that is independent in the matroid, with the objective of maximizing the total weight of covered edges. This problem is a generalization of the much studied max k-vertex cover problem, in which the matroid is the simple uniform matroid.

This problem is APX-hard and also W[1]-hard (with k being the paramter). Nonethess, in this work, by two different techniques, we are able to design Fixed-Parameter Tractable Approximation Schemes (FPT-AS).

This is joint-work with François Sellier at École des Mines.

Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki