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.

  • 1
    $\begingroup$ What do you mean by area? $\endgroup$ – copper.hat Jul 30 '12 at 8:12
  • $\begingroup$ @copper.hat: see my edit. $\endgroup$ – Helium Jul 30 '12 at 8:39
  • $\begingroup$ I don't know what it means for an algorithm to cover an area (or a volume, or anything else). How does an algorithm cover something? $\endgroup$ – Gerry Myerson Jul 30 '12 at 8:47
  • 1
    $\begingroup$ The convex hull of the first three points is two-dimensional, while that of the second four points is three-dimensional. Both of them have zero four-dimensional volume. You'll need at least five points to have nonzero volume in four-dimensional space. $\endgroup$ – user856 Jul 30 '12 at 8:49
  • 1
    $\begingroup$ Your update makes it an interesting and rather open-ended problem. I think volume, area, etc. may be the wrong tools for the job -- for example, adding the vector $\langle0,0,0,0\rangle$ to both data sets will probably increase these measures, but that's clearly not useful in terms of network throughput! Unfortunately I can't think of any alternatives to suggest off the top of my head. $\endgroup$ – user856 Jul 30 '12 at 9:18

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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