Title: The formulation complexity of minimum cut
Speaker: Ojas Parekh, Emory University
When: April 24, 12:30-13:30
Where: Porter Hall 125B
Abstract:
Our focus in this talk will be the size of linear programming formulations of combinatorial optimization problems. We may view this parameter as akin to traditional measures of complexity, such as computational time and space. We will focus on problems in P, in particular the minimum cut problem. For a graph $(V,E)$, existing linear formulations for the minimum cut problem require $\Theta(|V||E|)$ variables and constraints. These formulations can be interpreted as a composition of $|V|-1$ polyhedra for minimum $s$-$t$ cuts paralleling early algorithmic approaches to finding globally minimum cuts, which 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. Our formulation directly implies a smaller compact linear relaxation for the Traveling Salesman Problem that is equivalent in strength to the standard subtour relaxation.