SPOC 14 "Relations Min-max en optimisation combinatoire"

Date: 
Vendredi, 18 décembre, 2015

14ème séminaire du groupe POC

Le VENDREDI 18 DECEMBRE 2015

Au laboratoire LIP6 de l’Université Pierre et Marie Curie - Paris 6
4 place Jussieu Paris 6 (métro Jussieu)

Rotonde 26 - 1er étage - Couloir 25-26 - Salle 105

Sur le thème

Relations Min-max en optimisation 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:


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


 

10h00-10h50; a coffee break of 20mn; and the talk continue 11h10-12h00

András Frank
Eötvös Loránd University

MIN-MAX THEOREMS AND SUBMODULARITY

Submodular flows, introduced by Edmonds and Giles in 1977, provided a general framework that not only covers classic min-max theorems in network flows and in matroid theory but it helped deriving otherwise almost hopeless results.  A characteristic feature of this model is that not only the minimum cardinality optimization problem is tractable but the minimum cost or maximum weight version as well. Our first goal is to overview known and less known results of this type.

There are, however, natural min-max theorems where the cardinality case is nicely solvable while the min-cost version is NP-complete, and hence such results certainly cannot be derived from a framework appropriate to handling min-cost optimization problems.  For example, Eswaran and Tarjan found a min-max formula in 1976 for the minimum number of new arcs to be added to make an initial digraph strongly connected.  A less known example is the min-max theorem of Ryser from 1958 for the maximum term-rank of matrix which is about constructing a simple degree-specified bipartite graph in which the matching number
is as large as possible.

In the second part of the talk, we recall the supermodular arc-covering theorem by Frank and Jord\'an (1995) that turned out to be responsible for the solvability of several problems of this type. After outlining older applications, we describe new ones concerning degree-constrained and matroidal generalizations of the term-rank formula, packing cardinality-specified branchings, and various problems on connectivity augmentation with simple digraphs.

 

 


12h00-14h00     Repas


 

14h00 - 15h00

Denis Cornaz
LAMSADE, Université Paris-Dauphine

KÖNIG'S EDGE-COLOURING THEOREM FOR ALL GRAPHS

We show that the maximum degree of a graph  G is equal to the minimum number of ocm sets covering G, where an ocm set is the vertex-disjoint union of a matching and several odd cycles, and a collection of ocm sets covers G if every edge is in the matching of at least one ocm set or in some odd cycle of at least two ocm sets.
 

 


15h00 - 15h30     Pause


 

15h30 - 16h30

Mathieu Lacroix

LIPN, Université de Paris-Nord

TRADER MULTIFLOW AND BOX-TDI POLYHEDRA

A characterization of series-parallel graphs asserts that they are precisely the graphs for which the standard linear systems describing the cycle cone, the T-join polytope and the T-join dominant are TDI.
We prove that these systems are actually box-TDI.
As a consequence, the trader multiflow problem, which generalizes both the maximum and the minimum-cost multiflow problems is polynomial when the graph is series-parallel. In addition, we derive a min-max relation where the dual problem is a generalization of the multicut problem.
 

 


 

 

 

Si vous souhaitez proposer une présentation lors de cette journée, merci de contacter les organisateurs (baiou@isima.fr)

Le Groupe POC du GDR RO