1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Is $t$ specified, or are you allowed to select $t$ as part of the optimization? $\endgroup$
    – Brian Borchers
    Commented Apr 21, 2011 at 20:37
  • $\begingroup$ $t$ is specified $\endgroup$
    – arepo
    Commented Apr 22, 2011 at 0:53
  • $\begingroup$ 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.. $\endgroup$
    – Anadim
    Commented Apr 22, 2011 at 2:01

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .