SPOC 23 (ou 21bis) "Polyèdres et Combinatoire"

Date: 
Friday, 10 December, 2021

23ème séminaire du groupe POC

Le VENDREDI 10 DECEMBRE 2021

En distanciel et présentiel

En distanciel: avec zoom
En présentiel: Au laboratoire LAMSADE (Université Paris-Dauphine)
Place du Maréchal de Lattre de Tassigny 75017 PARIS

Sur le thème

Polyèdres et Combinatoire

 

Entrée gratuite
Merci de vous inscrire à cette journée pour faciliter l'organisation

Pour voir la liste des inscrits

Programme de la journée:


10h30-11h30

Michele CONFORTI
Università degli Studi di Padova

On the cut dominant and Steiner cuts

VIDEO: chaîne youtube POC

The cut dominant of a graph is the unbounded polyhedron whose points are all those that dominate some convex combination of cuts. Minimizing a nonnegative function over the cut dominant is equivalent to finding a minimum weight cut in the graph. We give a forbidden-minor characterization of the graphs whose cut dominant can be defined by inequalities with integer coefficients and right-hand side at most 2. Our result implies (and is closely related to) the forbidden-minor characterization of TSP-perfect graphs by Fonlupt and Naddef.
By restricting the set of terminals to a subset of vertices, one obtains the Steiner cut dominant. We present some results about the structure of these polyhedra.
 

11h30-12h00     Questions and discussion


12h00-13h30     Pause


13h30 - 14h30

András Sebő
Grenoble, France

Uniform Covers for Cones  and Combinatorial Problems:  Results, Connections and Challenges

PDF: Slide_Sebo_2021.pdf
VIDEO: chaîne youtube POC

A uniform cover is a family of sets so that every element is contained in the same number of members of the family.  We show some occurrences of uniform covers in combinatorial problems, mostly related to the gap between dual notions. Several results, connections and open problems will be presented.

 


14h30-15h00     Pause


15h00 - 16h00

Francisco  Barahona
IBM, USA

Packing hypertrees and the k-cut problem in Hypergraphs

VIDEO: chaîne youtube POC

We give an algorithm to find a maximum packing of hypertrees in a capacitated hypergraph.  Based on this we extend to hypergraphs several algorithms for the k-cut problem, that are based on packing spanning trees in a graph. In particular we give a γ-approximation algorithm for hypergraphs of rank γ. We also extend the work of Chekuri, Quanrud and Xu \cite{Chekuri} in graphs, to give an algorithm for the k-cut problem in hypergraphs that is polynomial if k and the rank of the hypergraph are fixed.

Joint work with M. Baiou
 


 

Lien sur fichier: