81 citations · 142 across the 18 of their papers we have counts for
7 papers · 1 filter
On the Complexity of Some Facet-Defining Inequalities of the QAP-polytope
Pawan Aurora, Hans Raj Tiwary
The Quadratic Assignment Problem (QAP) is a well-known NP-hard problem that is equivalent to optimizing a linear objective function over the QAP polytope. The QAP polytope with par…
Extension Complexity of Formal Languages
Hans Raj Tiwary
In this article we undertake a study of extension complexity from the perspective of formal languages. We define a natural way to associate a family of polytopes with binary langua…
Parameterized Extension Complexity of Independent Set and Related Problems
Jakub Gajarský, Petr Hliněný, Hans Raj Tiwary
Let be a graph on vertices and be the convex hull of characteristic vectors of its independent sets of size at most . We study extension complexity…
On the H-Free Extension Complexity of the TSP
David Avis, Hans Raj Tiwary
It is known that the extension complexity of the TSP polytope for the complete graph is exponential in even if the subtour inequalities are excluded. In this article we s…
A generalization of extension complexity that captures
David Avis, Hans Raj Tiwary
In this paper we propose a generalization of the extension complexity of a polyhedron . On the one hand it is general enough so that all problems in can be formulated as lin…
On Computing the Shadows and Slices of Polytopes
Hans Raj Tiwary
We study the complexity of computing the projection of an arbitrary -polytope along orthogonal vectors for various input and output forms. We show that if and are pa…
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 and a weight function on the edges $w:E\mapsto\RR$, we consider the polyhedron of negative-weight flows on , and get a complete characterization…