0
$\begingroup$

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.

$\endgroup$

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.