The vertex enumeration problem is to find the vertices of a set defined by a set of inequalities $\{x \in \mathbb{R}^n: Ax \le b\}$. It is an open question whether, if this set is known to be bounded, there is a polynomial time algorithm for doing this.

Suppose that I am constrained to use a polynomial time algorithm, but I can live with an underapproximation -- has there been any work that addresses this use case? That is, finding $v_1, ...$ such that

$$ \left\{\sum_i \lambda_i v_i : \sum_i \lambda_i = 1, \lambda_i \in [0, 1]\right\} \subsetneq \{x \in \mathbb{R}^n: Ax \le b\}. $$

Obviously, it would be good if these vertices gave as large a set as was possible, given the constraint to be polynomial time. This consideration leads to some sort of volume maximisation, subject to $Ax \le b$ type formulation that perhaps has an interpretation as a convex relaxation?

I am especially interested in solutions that remain firmly in matrix algebra and convex analysis, using only basic notions from matroids and other combinatorial notions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.