4
$\begingroup$

Given a set of vectors $\mathbf v_i$ for $i=1,\dots,k$, $\mathbf v_i \in \{0,1\}^n$, is that possible to efficiently find the volume of the set,

$\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\},$ such that $\sum_i \alpha_i=1$ and $\alpha_i \ge 0$. The comparison $\mathbf x \le \sum_{i=1}^k \alpha_i\mathbf v_i$ is taken componentwise.

Note: the above question arose from another question asked by me previously.

  • 0
    @Managu: Thanks for your comment. I don't know how to fix it either. Maybe it's not editable at all?2012-08-03

1 Answers 1

1

I believe we can reduce the stated problem to your initial question about finding the volume of a convex polytope.

First, the set you describe, call it $A$ is convex. In fact, we can specify a generating set for it. For each 0-1 vector $\mathbf b\in\{0,1\}^n$, let $p_\mathbf b(\mathbf x)=(x_1\cdot b_1, x_2\cdot b_2,\ldots,x_n\cdot b_n)$. That is, $p$ takes a vector $x$ and, in each place, replaces the coordinate with $0$ or leaves the coordinate alone, according to whether $b$ is $0$ or $1$. Then $A$ is the convex hull of $P=\left\{p_b(\mathbf{v}_i) : 0. Note that this set contains at most $k\cdot 2^n$ elements.

So we're back to, given a finite set, how do we calculate the volume of its convex hull? A little reading around suggests that this is a hard problem. See, e.g. https://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope.

  • 0
    Going in the other direction, the comple$x$ you describe subsumes the idea of the chain polytope of a poset, given in terms of the poset's maximal antichains. Which, is #P to compute given just a description of the poset (it has the same volume as the order polytope which your link talks about). But this doesn't prove hardness of your question -- a poset may have a number of maximal antichains exponential in its description size.2012-08-07