[5277] in Central_America
Re: New quotes for Sat Jan 22
mhpower@ATHENA.MIT.EDU (mhpower@ATHENA.MIT.EDU)
Tue Jan 25 14:53:26 1994
>mhpower: I'll bite ... what's the Mishloach Manot distribution problem?
Although the problem can be formulated in many different ways, I've
been looking at this approach. Consider a directed graph G comprised
of two or more points P, each having an internal structure consisting
of a base element PB and a set of zero or more child elements PC.
G is characterized by a minimum of one edge E(i,j) from each point
P(i) to one other distinct point P(j), and no edges from any point to
itself. Whenever PC(i) is nonempty, any edge from P(i) originates from
one of these child elements.
The points in G are further characterized by an affinity matrix A,
containing the probabilities that an edge from point P(i) will be
established to point P(j). At time t=0, row A[1] is searched for the
largest value associated with a point P(j) such that E(1,j) does not
yet exist. If such a value is found, E(1,j) is created. At the next
clock tick, A[2] is processed similarly, and so on. Also, once E(i,j)
is established, A is modified according to the update vector of P(j),
which indicates how much A[j,i] should be increased given that E(i,j)
has been created. Upon reaching the bottom row, the search cycles back
to A[1]. The algorithm terminates on reaching a preselected constraint
on the maximum number of edges originating from any one child element.
The problem is to order the points such that the total number of edges
in G is maximized. See also Esther 9.22.
