SPOC 14 "Relations Min-max en optimisation combinatoire"
Date:
Friday, 18 December, 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