Date : Jan. 26, 2017, 2 p.m. - Room :Salle du conseil

Reduced-size formulations for metric and cut polyhedra in sparse graphs

M. Viet Hung Nguyen - LIP6

Given a graph G=(V,E) of n vertices and m edges, we consider the metric cone MET(G) and the metric polytope METP(G) defined on the real space indexed by E. These polyhedra are relaxations of several important problems in combinatorial optimization such as the max-cut problem and the multicommodity flow problem. They are known to have non-compact formulations via the cycle inequalities in the original space inline image and compact (i.e., polynomial size) extended formulations via the triangle inequalities defined on the complete graph of n vertices. In this talk, we show that one can reduce the number of triangle inequalities to O(nm) and still have extended formulations for MET(G) and METP(G). We also present several extensions of the result for special graphs and for graph partitioning problem.