SPOC 21 "Polyèdres et Combinatoire"

Friday, 13 December, 2019

21ème séminaire du groupe POC


Au laboratoire LIP6 (Sorbonne Université)
4 place Jussieu 75005 Paris

Dans le campus Pierre et Marie Curie de Jussieu
Rotonde 26 - 1er étage - Couloir 25-26 - Salle 105

Sur le thème

Polyèdres et Combinatoire


Le séminaire est annulé compte tenu des difficultés de déplacements suite aux mouvements de grèves.


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:

9h30-10h30  Accueil "café - viennoiserie"



András SEBÖ
CNRS, Univ. Grenoble-Alpes, Laboratoire G-SCOP

Uniform Covers, Cones and Integrality Gap :  Connections and Challenges

A uniform cover is packing of combinatorial objects in graphs so that every edge is contained in the same number of objects. We show some relevant occurrences of uniform covers in combinatorial problems, their relation to polyhedra, to the integrality gap and to approximation ratios, and report about some recent results. Several related open problems will be stated.




LIPN, Université Paris 13

Characterizations of box-totally dual integral polyhedra

A polyhedron is box-integer if its intersection with any integer box is an integer polyhedron. We introduce principally box-integer polyhedra : they are the polyhedra whose dilatations are box-integer as soon as they are integer. We will present several characterizations of principally box-integer polyhedra, which involve matrices and strong integrality properties of linear sytems. In particular, this will provide new characterizations of box-totally dual integral polyhedra, which are polyhedra defined by linear systems having strong integrality properties.

This is a joint work with Patrick Chervet and Louis-Hadrien Robert.



12h00-14h00     Repas


14h00 - 15h00

Università degli Studi di Padova

The cut dominant and forbidden minors

The cut dominant of a graph is the unbounded polyhedron whose points are all those that dominate some convex combination of proper cuts. Minimizing a nonnegative linear 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 is related to the forbidden-minor characterization of TSP-perfect graphs by Fonlupt and Naddef. We prove that our result implies theirs, with a shorter proof. Furthermore, we establish general properties of forbidden minors for right-hand sides larger than 2.

This is joint work with Sam Fiorini and Kanstantsin Pashkovic


15h00 - 15h30     Pause


15h30 - 16h30

Faculty of Economics and Business, KU Leuven, Belgique

Convex Hull Results for Generalizations of the Constant Capacity Single Node Flow Set

For single node flow sets with fixed costs and constant capacities on the inflow and outflow arcs, a family of constant capacity flow covers are known to provide the convex hull in different special  cases and are conjectured to provide it in the general case. Here we study more general mixed integer sets for which such single node flow cover inequalities suffice to give the convex hull. In particular we consider the case of  a path in which each node has one (or several) incoming and outgoing arcs with constant capacities and fixed costs. This can be seen as a lot-sizing set with production and sales decisions driven by costs and prices and  by the lower and upper bounds on stocks instead of being driven by demands as in the standard lot-sizing model. To describe the convex hulls, we characterize the extreme points, derive tight extended formulations and project out the additional variables using Fourier-Motzkin elimination. The validity of the conjecture for the single node flow set follows from our results.

This is joint work with Laurence A. Wolsey.


16h30 - 17h30

Mourad BAIOU
CNRS, Laboratoire LIMOS, Université Clermont-Auvergne

On some network security games

We study two-players games on graphs, where one player (the defender) chooses a tree, and (simultaneously) the other  player (the attacker) chooses an edge hoping to detect the defender. For each edge e there is a probability p(e) that the attacker will detect the defender if both players have chosen
the edge e. Also the attacker incurs on a cost c(e) if he chooses the edge e. The defender has to find a tree-selection strategy that minimizes the average probability of being detected. The attacker has to find a probabilistic selection strategy that maximizes the average detection probability minus its average  cost. We give polynomial algorithms to find both strategies. We also extend this to security games on matroids.