SPOC 21 "Polyèdres et Combinatoire"
Date:
Friday, 13 December, 2019
21ème séminaire du groupe POC
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
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"
10h00-11h00
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.
11h00-12h00
Roland GRAPPE
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
Michele CONFORTI
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
Hande YAMAN
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.