MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEFrom Pyramids to Virtual Private Network Polyhedra
par Andras Sebo
| Date : | 20/10/11 | | Time : | 10:00 | | Location : | Galois Coriolis |
The celebrated VPN Tree Conjecture raised by Fingerhut, Suri and Turner, and then again by A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yenerhas has been proved by N. Goyal, N. Olver, and B. Shepherd using an intermediate station, the equivalence of the so called ''Pyramidal Conjecture'' by F. Grandoni, V. Kaibel, G. Oriolo, and M. Skutella (later a shortcut has been observed using a result of Padberg and Rao).
Roughly, the problem consists in designing paths between a given set of terminals so as to minimize the cost of capacities to be bought when routing a demand function between the terminals through the designed paths -- satisfying certain linear constraints.
Until now the results have been built as a pyramid using bricks from previous work as black boxes (or black bricks), finishing with properties of minimum weight T-cuts based on Gomory-Hu trees. With my coauthors we redigested the subject with a polyhedral insight that leads to a simpler elementary proof and sharpening the results. The black boxes are opened, the proof pyramid collapses to determining the extreme points of a polytope.
It turns out that the problem has a natural formulation as optimizing on a convex polytope whose vertices correspond to Steiner-trees of the network. Besides the connexion to polyhedral combinatorics, this new look on the problem yields simple proofs, sharper results and leads to new questions.
This is joint work with Nicola Apollonio, Fabrizio Grandoni and Gianpaolo Oriolo.
Page des séminaires
| 
