Skip to main content
1 of 7
kakia
  • 399
  • 2
  • 15

$L2$-norm vs. $L_\infty$-norm

There are $n$ positive real numbers. We want to partition these numbers into $m$ parts so that if sum up numbers inside each part the maximum sum is minimized, and we call this maximum sum (it is called makespan) $L_\infty$ norm of a sequence. Similarly, we want to partition these numbers in $m$ parts so that the sum of squares of the sums is minimized, and call the maximum sum a $L_2$ norm.

Second partition also somehow tries to balance the loads in each part, 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$ norm 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}$. I think there should be a different (and easier) analysis which achieves better bounds or even closes the question.

kakia
  • 399
  • 2
  • 15