Skip to main content
4 of 7
added 95 characters in body
kakia
  • 399
  • 2
  • 15

$L_2$ vs. $L_\infty$

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).

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.

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$.

kakia
  • 399
  • 2
  • 15