1
$\begingroup$

Consider the standard 2-simplex $\{(x,y)~|~x+y=1~;~ x,y\geq 0\}$. Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y by the following process:

  • Fix two positive weights $(w_x,w_y)$;
  • For each point $(x,y)\in M$, calculate $w_x x$ and $w_y y$;
  • If $w_x x > w_y y$ then give the point to X; else give the point to Y.

From the set of $2^m$ possible allocations, only $m+1$ allocations can be attained by the above procedure. Why? Because if a point $(x_1,y_1)$ is given to X, then all the points $(x_2,y_2)$ with $x_2>x_1,y_2<y_1$ are given to X too. Thus, each allocation can be found by cutting the line at some point, giving to X all the points between the cut and $(1,0)$, and giving to Y the remaining points. Thus, it is easy to enumerate all possible allocations.

The question is: what happens when we move to a higher-dimensional simplex? For example, consider the standard 3-simplex $\{(x,y,z)~|~x+y+z=1~;~ x,y,z\geq 0\}$. Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y or to Z by the following process:

  • Fix 3 positive weights $(w_x,w_y,w_z)$;
  • For each point $(x,y,z)\in M$, calculate $w_x x$ and $w_y y$ and $w_z z$;
  • If $w_x x$ is larger than the other two - give the point to X; else, if $w_y y$ is larger than $w_z z$ - give the point to Y; else, give the point to Z.

What is an efficient algorithm, with run-time polynomial in the output size, for enumerating all and only the allocations attainable by the above procedure?

$\endgroup$
1
$\begingroup$

I'd suggest using a recursive search. Suppose you have a subset of $k$ of the points and a proposed allocation for those $k$ points into X/Y/Z. Then you can test whether there exists $w_x,w_y,w_z$ that would lead to that allocation, by testing feasibility of a linear program. (For the allocation to be feasible, there are a bunch of linear inequalities that must hold on the variables $w_x,w_y,w_z$; test whether these can all simultaneously hold.)

Now, given a feasible allocation for $k$ points, pick one more point and try all three possibilities for whether that additional point is allocated to X, Y, or Z. (In other words, you extend it to three possible allocations on $k+1$ points.) Test which ones are feasible, and recurse on each of the feasible ones.

One can show that if there are $N$ feasible allocations in all, then this process will require at most $3mN$ recursive invocations. Each recursive invocation involves solving a linear program, which can be done in polynomial time. Thus, we obtain a procedure whose running time is polynomial in the number of feasible allocations. The same result generalizes to more than three dimensions.

$\endgroup$
  • $\begingroup$ If I understand correctly, your algorithm does a depth-first search on the tree of allocations. In this tree, each node in depth $i$ corresponds to a feasible allocation of points $1,...,i$. The root is the empty allocation. Each node in depth $i<m$ has at most 3 children - one for each possible allocation of point $i+1$. There are $N$ leaves - one for each complete feasible allocation. Is this description correct? $\endgroup$ – Erel Segal-Halevi Mar 9 at 23:10
  • $\begingroup$ @ErelSegal-Halevi, yup. Except, once we find that a partial allocation is not feasible, we don't explore anything under that node. It's easy to see that if there are N feasible allocations, then we only visit nodes that are ancestors of those N leaves (plus their siblings), and the number of those is the height of the tree times N times the branching factor of the tree. (I've corrected a small error in the last paragraph of my answer regarding the number of recursive invocations.) $\endgroup$ – D.W. Mar 9 at 23:16
  • $\begingroup$ Great answer, and a useful general technique. Thanks. How can I cite your answer in a paper? $\endgroup$ – Erel Segal-Halevi Mar 13 at 10:42
  • $\begingroup$ @ErelSegal-Halevi, glad it helped! You could cite this this question/answer (see e.g. the "cite" link under the question and answer). $\endgroup$ – D.W. Mar 13 at 15:47
0
$\begingroup$

From the set of $2^m$ possible allocations, only $m+1$ allocations can be attained by the above procedure. Why?

The boundary between the two halves of the allocation is the line $w_xx = w_yy$; the point $(x, y)$ only crosses from one half to the other when it's on the boundary, so we can sort the points by $\tan^{-1}(y,x)$.

Now, lift this into 3D. Without loss of generality, either $w_x = 0$ and it reduces to the 2D situation, or $w_x = 1$. In the latter case, for each allocation between X and Y we have $\frac{x_i}{y_i} \le w_y < \frac{x_{i+1}}{y_{i+1}}$. Now we consider the range of values which $w_z$ can take. The points allocated to X can be sorted by the value of $w_z$ at which they are on the boundary, and the points allocated to Y can be sorted by the value of $w_z$ at which they are on the boundary for an arbitrary fixed $w_y$. We can combine the chains by using the constraints on the possible range of $w_y$ to place cross-chain constraints: for each point allocated to Y, find the latest point allocated to X which is forced to precede it, and the earliest point allocated to X which is forced to follow it. Then the possible allocations between X,Y,Z are given by the possible topological sorts on the resulting DAG with cutoffs for Z.

$\endgroup$
  • $\begingroup$ What is $i$ in the second paragraph? And, what is the "resulting DAG with cutoffs for Z"? $\endgroup$ – Erel Segal-Halevi Mar 9 at 23:21
  • $\begingroup$ $i$ is the loop variable indicating where you make the allocation division between X and Y. Effectively, it's the number of points allocated to X in the initial X-Y allocation. You're mis-parsing the ambiguous noun phrase in the last sentence: it's (the possible topological sorts on the resulting DAG) with (cutoffs for Z). For each topological sort you do the same thing of picking one of the $n+1$ places to allocate between (X+Y) vs Z. But the topo. sorts aren't independent: if you choose to allocate the first three points to Z, you don't care about the order of points beyond the cutoff. $\endgroup$ – Peter Taylor Mar 9 at 23:48
  • $\begingroup$ OK. So the algorithm has two steps: constructing a DAG where the nodes are the $m$ points, and finding all topological sorts in that DAG. Is it correct? $\endgroup$ – Erel Segal-Halevi Mar 11 at 17:42

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.