Wednesday, 16:15 - 16:40 h, Room: H 3013


Shanfei Li
The polyhedral relationship between the capacitated facility location polytope and its knapsack and single-node flow relaxations

Coauthor: Karen Aardal


The knapsack and single node flow polytopes, XK and XSNF respectively, are well-known relaxations of the capacitated facility location polytope XCFL. In earlier studies specific classes of facets for XK and XSNF have been proved to be facets also for XCFL, and the computational effectiveness of these classes have also been demonstrated for XCFL. In this presentation
we prove more general relationships between the polytopes XK, XSNF, and XCFL. We also prove results in the spirit of Goemans' worst-case comparison of valid inequalities.


Talk 3 of the contributed session Wed.3.H 3013
"Polyhedra in combinatorial optimization" [...]
Cluster 2
"Combinatorial optimization" [...]


  quick loans . Cialis Professional online is capableto release you reliably from the erection problems, its improved formula gives the new properties to the drug.