# Computing the volume of a set efficiently

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.

-
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? – Helium Aug 3 '12 at 20:16

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.

-
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? – Helium 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
The text passage contains a mathematical question about efficiently finding the volume of a specific set defined by a set of vectors. There is no direct answer provided to this question within the text, but there are comments and discussions that provide insights and related information.
single_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Computing the volume of a set efficiently

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.

-
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? – Helium Aug 3 '12 at 20:16

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.

-
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? – Helium 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
user
The text passage contains a mathematical question about efficiently finding the volume of a specific set defined by a set of vectors. There is no direct answer provided to this question within the text, but there are comments and discussions that provide insights and related information.

TYPE: SINGLE_QUESTION