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.
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:
