Date:

Vendredi, 13 décembre, 2019

**Le VENDREDI 13 DECEMBRE 2019**

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

**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"**

**10h00-11h00**

**András SEBÖ**

CNRS, Univ. Grenoble-Alpes, Laboratoire G-SCOP

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.

**11h00-12h00**

**Roland GRAPPE **

LIPN, Université Paris 13

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**

**Michele CONFORTI**

Università degli Studi di Padova

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**

**Hande YAMAN**

Faculty of Economics and Business, KU Leuven, Belgique

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

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.