 | Greetings,
Here's my problem definition:
Fixed: positive integers N, r, B where N >= 3, 2r <= B <= 5r
Variable:
token increment sequence (r_0,...,r_{N-1}),
bucket depth sequence (B_0,...,B_{N-2}), both sequences of
non-negative integers that satisfy
\sum_{i=0}^{N-1} r_i = Nr
\sum_{i=0}^{N-2} B_i = (N-1)B
To maximize: g_0(0), where
g_N(t) = 1 and
g_k(t) = \sum_{l=0}^{t+r_k} 2^l g_{k+1}(min(t + r_k - l,B_k)) for
k=0,1,...,N-1 (Take B_{N-1} = \infty)
Based on my computations, I observed that every optimal solution
(multiple optimal solutions can exist) satisfies the following
properties:
1. When B = 2r, the bucket depth sequence is uniform (B_0 = B_1 = ... =
B_{N-2}).
2. When B > 2r, the bucket depth sequence is uniform or near-uniform
(standard deviation is low compared to the mean).
3. The token increment sequence is a non-increasing sequence.
If you have any idea of the techniques (say from integer programming,
combinatorial optimization) which can be used to prove the above
properties, pls. let me know.
Examples:
When N=4, r=5, B=10, the optimal tok.inc. and buck.dep. sequences are
(10 5 5 0) and (10 10 10) resp. However, if we change the value of B to
12, the optimal sequences are (11 6 3 0) and (11 14 11) resp.
Remarks (from another set of computations):
If B=2r and we fix the tok.inc. sequence, then the buc.dp. sequence
which maximizes g_0(0) is not necessarily uniform. Thus, only the
optimal solution (of the original problem) has the beauty of satisfying
property #1.
thanks,
Ashutosh
adgoreATeeDOTiitbDOTacDOTin
|
|
