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
    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
    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
    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
    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
    Sep 22, 2016 at 14:15

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.