Hans Raj Tiwary

most citedOn the extension complexity of combinatorial polytopes

23 citations · 23 across the 3 of their papers we have counts for

collaborators

3 papers

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…

cs.CG2008

On Computing the Vertex Centroid of a Polyhedron

Khaled Elbassioni, Hans Raj Tiwary

Let $P$ be an $H$ -polytope in $R^{d}$ with vertex set $V$ . The vertex centroid is defined as the average of the vertices in $V$ . We prove that computing…

cs.CC2008

Characterization of the Vertices and Extreme Directions of the Negative Cycles Polyhedron and Hardness of Generating Vertices of 0/1-Polyhedra

Endre Boros, Khaled Elbassioni, Vladimir Gurvich +1

Given a graph $G = (V, E)$ and a weight function on the edges $w:E\mapsto\RR$, we consider the polyhedron $P (G, w)$ of negative-weight flows on $G$ , and get a complete characterization…