Name
Abstract | ||
|---|---|---|
Given a graph G=(V,E) with |V|=n and |E|=m, we consider the metric cone MET(G) and the metric polytope METP(G) defined on RE. 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 RE and compact (i.e. polynomial size) extended formulations via the triangle inequalities defined on the complete graph Kn. In this paper, 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). This is particularly interesting for sparse graphs when m=O(n). |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.endm.2016.03.017 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
metric polytope,triangle inequalities,maxcut problem,extended formulation | Discrete mathematics,Complete graph,Graph,Combinatorics,Polynomial,Polyhedron,Combinatorial optimization,Polytope,Triangle inequality,Multi-commodity flow problem,Mathematics | Journal |
Volume | ISSN | Citations |
52 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Viet Hung Nguyen | 1 | 108 | 18.79 |
| Michel Minoux | 2 | 741 | 100.18 |
| Dang Phuong Nguyen | 3 | 0 | 0.34 |