1

1

Given a sum of $l$ integers $r_1+...+r_k+...+r_l$ and an integer $t$.

Find indices

$1 < p_1 <...< p_h <...< p_{t-1} < l$

such that in sum

$(r_1+...+r_{p_1})+...+(r_{p_{h-1}+1}+...+r_{p_h})+...+(r_{p_{t-1}}+...+r_l)$

sums in brackets have nearly same value.

The criteria "nearly same value" can be defined by some norm over the vector of sums $(R_1,...,R_h,...,R_t)$, where $R_h=(r_{p_{h-1}+1}+...+r_{p_h})$.

Do you know something about this problem? Any similar problems? Any suitable references on such problems? To what problems this can be reduced?

flag
Is $t$ specified, or are you allowed to select $t$ as part of the optimization? – Brian Borchers Apr 21 2011 at 20:37
$t$ is specified – arepo Apr 22 2011 at 0:53
One different way of thinking this problem is the following. You have a full bipartite graph. The nodes on the left side represent your $l$ $r_l$ numbers and the vertices on your right represent your $t$ sets. The weights of the edge $e_{i,j}$ is the value $r_i$. Your objective now is to find something like a cardinality and weight "balanced" set cover comprising of $t$ sets. I'm not sure though if this can give you any further insights.. – Anadim Apr 22 2011 at 2:01

1 Answer

1

For a great result for $t=2$, see this paper by Gyula Karolyi.

link|flag

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.