Calcular el volumen de un conjunto de manera eficiente

Question

Dado un conjunto de vectores $\mathbf v_i$ $i=1,\dots,k$, $\mathbf v_i \in \{0,1\}^n$, es posible buscar de forma eficiente el volumen del conjunto,

$$\left\{\mathbf x \in [0,1]^n:\mathbf x \le \sum_{i=1}^k \alpha_i\mathbf v_i\ \text{for some $\alpha_i$}\right\},$$ tal que $\sum_i \alpha_i=1$$\alpha_i \ge 0$. La comparación de $\mathbf x \le \sum_{i=1}^k \alpha_i\mathbf v_i$ es tomado de las componentes.

Nota: la anterior pregunta surgió a partir de otra pregunta se le preguntó por mí anteriormente.

Answer 1

Creo que podemos reducir el problema planteado a su pregunta inicial acerca de cómo encontrar el volumen de un convexo polytope.

En primer lugar, el conjunto de describir, se $A$ es convexa. De hecho, podemos especificar un grupo electrógeno. Para cada 0-1 vector $\mathbf b\in\{0,1\}^n$, vamos a $p_\mathbf b(\mathbf x)=(x_1\cdot b_1, x_2\cdot b_2,\ldots,x_n\cdot b_n)$. Es decir, $p$ toma un vector $x$ y, en cada lugar, sustituye a la de coordinar con $0$ o sale de la coordenada solo, de acuerdo a si $b$ $0$ o $1$. A continuación, $A$ es el casco convexo de $P=\left\{p_b(\mathbf{v}_i) : 0<i\leq k, \mathbf{b}\in \{0,1\}^n\right\}$. Tenga en cuenta que este conjunto contiene a la mayoría de las $k\cdot 2^n$ elementos.

Así que estamos de vuelta para, dado un conjunto finito, ¿cómo podemos calcular el volumen de su casco convexo? Un poco de lectura en torno sugiere que este es un problema difícil. Ver, por ejemplo, http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope.