Combinatorial versus Ellipsoid Polynomial Algorithms

Mardi 29 octobre 2019, 14h, en salle A413

Thomas McCormick (Sauder School of Business, the university of british columbia canada)

Abstract :

 

The Ellipsoid Algorithm is a useful way to prove that a problem has a 
polynomial algorithm, but such algorithms don't work well in practice. 
Hence, we should be trying to find "combinatorial" polynomial algorithms 
for such problems.  There are also cases where we already have a 
combinatorial polynomial algorithm, but we don't have the "dual" 
description of the underlying polyhedra.  In this talk I'll describe 
some notable successes (Submodular Function Minimization, Abstract Flow, 
Lattice Polyhedra), and some open problems (Schrijver's TDI framework, 
Subtour Elimination, 2-Dimensional Precedence-Constrained Scheduling), 
and I'll make some suggestions on how to attack such open problems.

[version française]

Algorithmes Polynomiaux Combinatoires Et Ellipsoïdes

L'algorithme d'ellipsoïde est un moyen utile de prouver qu'un problème a 
un algorithme polynomial, mais de tels algorithmes ne fonctionnent pas 
bien dans la pratique. Par conséquent, nous devrions essayer de trouver 
des algorithmes polynomiaux "combinatoires" pour de tels problèmes. Il 
existe également des cas où nous avons déjà un algorithme combinatoire 
polynomial, mais nous n'avons pas la description "dual" des polyèdres 
sous-jacents. Dans cet exposé, je décrirai quelques succès notables 
(minimisation de fonctions sous-modulaires, flux abstrait, polyhèdres de 
trellis) et quelques problèmes ouvertes (cadre de TDI de Schrijver, 
élimination de sous-tour, ordonnancement à prédominance 
bidimensionnelle), et je ferai quelques suggestions sur la manière 
d'attaquer ces problèmes ouverts.