2
$\begingroup$

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
    What do you mean by area?2012-07-30
  • 0
    @copper.hat: see my edit.2012-07-30
  • 0
    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?2012-07-30
  • 1
    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.2012-07-30
  • 0
    @RahulNarain: I added a brief description about why one algorithm gives 3 vectors while the other gives 4 vectors as the output. It is actually somewhat technical and I cannot describe more details. But this is the issue that I have to deal with. I am looking for a fair/reasonable measure to compare the algorithms. I need to add that 3 and 4 are just special cases. In general, we can have more vectors.2012-07-30
  • 1
    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.2012-07-30
  • 0
    @RahulNarain: As you mentioned volume/area is a wrong tool. Thanks for your comments that made the issue clear for me too. Just to complete your comment, assume an algorithm gives only one vector $⟨1,1,1,1⟩$. That's the best solution but it's volume/area is absolutely zero.2012-07-30

1 Answers 1