I have 2 algorithms for a problem. A solution to the problem is a set of n-dimensional vectors of 0/1's. A given solution covers any point inside the convex hull of the n-dimensional solution vectors. I want to find out, which algorithm covers a larger area. For instance, assume in the 4d space, algorithm 1 gives the solution:
$$\langle 1,0,0,1 \rangle,\langle 0,1,0,1 \rangle,\langle 0,0,1,0 \rangle$$
while algorithm 2 gives,
$$\langle 1,0,1,1 \rangle,\langle 0,1,0,1 \rangle,\langle 1,1,0,0 \rangle,\langle 1,0,1,1 \rangle$$
The question is that which algorithm covers a larger area? And by how much?
Edit:
Given a set of n-dimensional vectors $\mathbf v_1,\mathbf v_2,\dots,\mathbf v_k$ as the solution, the solution covers any point,
$$\alpha_1 \mathbf v_1+\alpha_2 \mathbf v_2+\dots+\alpha_k \mathbf v_k$$
satisfying the condition $\alpha_1+\dots+\alpha_k=1$. I just don't know if I should use the term "area" or "volume" for the set of points that are covered by the solution.
Edit 2:
The problem above actually is related to a real problem in computer networks. Assume in a computer network, because of some technical issues, we can enable only some of the users at any time. In the above example, for instance, $\langle 0,1,0,1 \rangle$ means users 2 and 4 can be enabled while users 1 and 3 must be disabled. Enabling a user means the user can transmit at rate 1 while disabling means rate 0 (generally the $i$th cell in the vector shows the rate of user $i$). In addition, we can use any of the vectors for a portion of time. This makes a convex hull of the given vectors. If a point is inside the convex hull, it means that the network can support the rates requested by the point (by choosing appropriate portion of time for each vector). Otherwise, the network cannot support the requested rate.
Best Answer
Here's an idea related to the concept of Pareto efficiency that should work for your application. To support a requested rate $\mathbf x$, you don't really need $\mathbf x = \sum \alpha_i\mathbf v_i$ exactly for some $\alpha_i$; it is enough to have $\mathbf x \le \sum \alpha_i\mathbf v_i$ where the comparison is taken componentwise. That is, every component of $\mathbf x$ is at most the corresponding element of $\sum \alpha_i\mathbf v_i$; every user gets at least as much bandwidth as they asked for. So instead of the convex hull, you should look at 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\}.$$ I believe, though I haven't proved, that this is nonzero as long as there is no component for which all $\mathbf v_i$ are zero, and equals $1$ if and only if one of the $\mathbf v_i$ equals $\langle1,1,\ldots,1\rangle$. I'm not sure how to efficiently compute this, however; if you think this would be the right metric for you to use, you may want to ask a new question about how to compute it.