11
$\begingroup$

There are $n$ positive real numbers. We partition these numbers into $m$ parts, the size of each part is the sum the numbers in this part. Maximum size of the parts is called a makespan of a partition. We consider two different partitions, one is that minimizes makespan, and we call this number $L_\infty$. Similarly, second partition minimizes sum of the squares of the part sizes, and call the maximum size $L_2$ (because it is a makespan of a partition which minimizes $L_2$-norm). In case of ties, we choose a distribution which gives larger makespan.

Second partition also somehow balances the loads in all parts, though it sometimes gives a larger makespan than the optimum.

Example: suppose $n=6$, $m=3$ and the numbers are $13$, $9$, $9$, $6$, $6$, $6$. Then the $L_\infty$ is $18$ because we can partition these numbers in $3$ parts like $(13), (9,9), (6,6,6)$, while the partition which minimizes sum of the squares is $(13,6), (9,6), (9,6)$, i.e. $L_2/L_{\infty}$ = 19/18 in this case.

My question is: what is the largest possible value for ${L_2}/{L_\infty}$? In a recent short paper, me and my colleague showed that this value can be as large as $\frac{7}{6}$ while it can not be larger than $\frac{4}{3}$. http://www.sciencedirect.com/science/article/pii/S0167637716300712 this is a link to a paper, though I think method used in it can not improve the bounds, because we only consider local constraints, inequalities obtained from possible configurations on 2 or 3 machines. We do not have any global inequality.

I think there should be a different (and maybe easier) analysis which achieves better bound(s) or even closes the question.

I believe the upper bound is also $7/6$.

Improve this question
$\endgroup$
6
  • $\begingroup$ A more informative title would be welcome (it looked like something about Banach spaces). $\endgroup$
    – YCor
    Commented Sep 8, 2016 at 15:54
  • $\begingroup$ Just to get the definitions of $L_2$ right: if two different partitions minimize the sum of squares, what is the definition of $L_2$ if the maximum sizes in these partitions are different. For example take $m=3$ and consider $4, 4, 5, 6, 7, 10$. Both $(4,7),(5,6),(4,10)$ and $(4,4,5),(6,7),(10)$ minimize sum of squares (since $11^2+11^2+14^2=438=10^2+13^2+13^2$) the maximum size in the partitions are 14 or 13. Which one would be $L_2$? $\endgroup$
    – Moritz Firsching
    Commented Sep 22, 2016 at 8:00
  • $\begingroup$ In case of ties, you can consider the worst(largest makespan) one, in this case you could say $L_2$ is $14$. $\endgroup$
    – kakia
    Commented Sep 22, 2016 at 10:54
  • $\begingroup$ Is it known what the largest possible value of $L_2/L_\infty$ if we fix $n=6$ and $m=3$? $\endgroup$
    – Moritz Firsching
    Commented Sep 22, 2016 at 13:16
  • $\begingroup$ Computer experiments suggested that it should be 13/12, matching with the lower bound example we give in the paper(the general lower bound converges to 7/6, though). We didn't try to prove it for fixed $m$ and $n$, but it also seemed that if $m$ is fixed, then the best $n$ is equal to $2m$. $\endgroup$
    – kakia
    Commented Sep 22, 2016 at 14:15

0

Reset to default

You must log in to answer this question.