Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
To all concerned: This is the union of the boxes $[0,x_1]\times[0,x_2]\times\cdots\times[0,x_n]$ for all $\mathbf x=(x_1,x_2,\ldots,x_n)$ in the convex hull of the input vectors. –  Rahul Aug 1 '12 at 8:43
    
Perhaps more intuitively, it is the set of points dominated (in the sense of Pareto efficiency) by said convex hull. –  Rahul Aug 2 '12 at 0:44
    
@Managu: Thanks for your comment. I don't know how to fix it either. Maybe it's not editable at all? –  Mohsen Aug 3 '12 at 20:16
add comment

1 Answer 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<i\leq k, \mathbf{b}\in \{0,1\}^n\right\}$. 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. http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope.

share|improve this answer
    
Yes, the problem looks #P in general(renyi.hu/~miki/kopenwww.pdf). But I wonder, my problem, as a special case is hard as well? –  Mohsen Aug 3 '12 at 21:17
    
Everything I've looked at suggests that really bad behavior tends to happen as the dimension goes up moreso than as the number of points goes up. And a lot of the funky examples are given in the halfspace representation of a polytope, instead of the vertex representation as I'm discussing here. If your dimension is fixed, I suspect the volume can be computed in time poly(|V|). –  Managu Aug 7 '12 at 2:22
    
Going in the other direction, the complex 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. –  Managu Aug 7 '12 at 3:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.