Date: Mon, 21 Feb 2000 18:46:33 PST

From: john lee

I have two problems which are related, one is 1-D case, another is 2-D case. In the problems I want to get the lower and upper bound of variables.

There have N variables C_{i}, i=1,2,...N.
C_{i} is a real number.
At the beginning, C_{i} is 0 for all i.

Associating with every C_{i}, there has a p_{i}, which is a non-negative real
number.
And the summary of all p_{i} is exactly 1, i.e.,
\sum_{i=1}^{i=N} p_{i} = 1.

At the beginning of every second, C_{i} increase by p_{i}, i.e.,
C_{i} = C_{i} + p_{i}.

Then, the C_{i} with the maximum value is selected. (Ties are broken randomly)
The selected C_{i} (only one will be selected) will decrease by 1, and all
others are unchanged:
we select i, where C_{i} >= C_{j}, for all j,
then let C_{i} = C_{i} - 1.

So, we know that at the end of every second, the summary of all C_{i} is
exactly 0. But for every individual C_{i}, it can be 0, negative, or positive.

I want to know whether we can find the tight lower and upper bound of C. I can prove that the lower bound is -1, and upper bound is N/2. But by simulation, I found the upper bound is very close to 1. (It's larger than 1) Can you show me how to prove a tight upper bound?

There has an NxN array [C_{i,j}].
C_{i,j} is real number for all i,j.
At the beginning, C_{i,j} is 0 for all i,j.

Associating with every C_{i,j}, there has a p_{i,j}.
p_{i,j} is a non-negative real number.
And the summary of p_{i,j} in every column and every raw is exactly 1, i.e.,
\sum_{i=1}^{i=N} C_{i,j} = 1 \forall j, and
\sum_{j=1}^{j=N} C_{i,j} = 1 \forall i.

At the beginning of every second, C_{i,j} increases by p_{i,j}, i.e.,
C_{i,j} = C_{i,j} + p_{i,j}

Then a matching is found. The matching is defined as following: From the NxN array, we select exactly N elements, where in every column there has exactly one element selected, and in every raw there also has exactly one element selected.

There has a large number of possible matchings for a large N.
In this problem we try to find the Maximum Weight Matching (MWM).
Where from all the matchings, we find the matching that can maximize the
summary of C_{i,j}.

Then, after the matching is selected, C_{i,j} will decrease by 1, if (i,j)
is in the matching.

So, at the end of every second, the summary of C_{i,j} in every column and
raw is exactly 0.

I want to know whether we can find the lower bound and upper bound of C.

By simulations, I found that the lower bound is larger than -2, and the upper bound is about +4.

In the simulations I set N to 16 and 32.