Name
Abstract | ||
|---|---|---|
For a graph (V,E), existing compact linear formulations for the minimum cut problem require Θ(|V||E|) variables and constraints and can be interpreted as a composition of |V| − 1 polyhedra for minimum s-t cuts in much the same way as early approaches to finding globally minimum cuts relied on |V| − 1 calls to a minimum s-t cut algorithm. We present the first formulation to beat this bound, one that uses O(|V|2) variables and O(|V|3) constraints. An immediate consequence of our result is a compact linear relaxation with O(|V|2) constraints and O(|V|3) variables for enforcing global connectivity constraints. This relaxation is as strong as standard cut-based relaxations and has applications in solving traveling salesman problems by integer programming as well as finding approximate solutions for survivable network design problems using Jain's iterative rounding method. Another application is a polynomial-time verifiable certificate of size n for for the NP-complete problem of l1-embeddability of a rational metric on an n-set (as opposed to a certificate of size n2 known previously). |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1541885.1541888 | Symposium on Discrete Algorithms |
Keywords | Field | DocType |
compact linear relaxation,salesman problem,minimum cut problem,size n,polynomial-time verifiable certificate,linear programming formulation complexity,minimum s-t cut algorithm,new linear formulation,minimum cut,compact linear formulation,minimum s-t cut,np-complete problem,compacting cut,traveling salesman problem,polynomial time,linear program,np complete problem | Discrete mathematics,Combinatorics,Network planning and design,Polyhedron,Minimum cut,Rounding,Travelling salesman problem,Verifiable secret sharing,Integer programming,Mathematics,Certificate | Journal |
Volume | Issue | ISSN |
5 | 3 | 1549-6325 |
Citations | PageRank | References |
4 | 0.54 | 25 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert Carr | 1 | 566 | 55.31 |
| Goran Konjevod | 2 | 779 | 57.82 |
| Greg Little | 3 | 1420 | 96.33 |
| Venkatesh Natarajan | 4 | 7 | 1.39 |
| Ojas Parekh | 5 | 192 | 22.05 |