81 citations · 142 across the 18 of their papers we have counts for
Showing math.COShow all
3 papers · 1 filter
math.CO2026
Bond Polytope under Vertex- and Edge-sums
Petr Kolman, Hans Raj Tiwary
A cut in a graph is called a {\em bond} if both parts of the cut induce connected subgraphs in , and the {\em bond polytope} is the convex hull of all bonds. Computing the m…
math.CO2013★ 23 cited
On the extension complexity of combinatorial polytopes
David Avis, Hans Raj Tiwary
In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponen…
math.CO2011★ 6 cited
Exponential Lower Bounds for Polytopes in Combinatorial Optimization
Samuel Fiorini, Serge Massar, Sebastian Pokutta +2
We solve a 20-year old problem posed by Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman p…