# relaxation of vertex enumeration problem?

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.