Skip to main content
Notice removed Draw attention by CommunityBot
Bounty Ended with no winning answer by CommunityBot
added discussion from the comment, refined a definition.
Source Link
kakia
  • 399
  • 2
  • 15

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

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

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

Notice added Draw attention by kakia
Bounty Started worth 50 reputation by kakia
added some discussion
Source Link
kakia
  • 399
  • 2
  • 15

$L_2$ minimizing makespan vs. $L_\infty$ minimizing makespan in load balancing

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

$L_2$ minimizing makespan vs. $L_\infty$ minimizing makespan in load balancing

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

$L_2$ minimizing makespan vs. $L_\infty$ minimizing makespan

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

title change
Link
kakia
  • 399
  • 2
  • 15

$L_2$ minimizing makespan vs. $L_\infty$ minimizing makespan in load balancing

added 95 characters in body
Source Link
kakia
  • 399
  • 2
  • 15
Loading
added 196 characters in body; edited title
Link
kakia
  • 399
  • 2
  • 15
Loading
added 196 characters in body; edited title
Source Link
kakia
  • 399
  • 2
  • 15
Loading
Source Link
kakia
  • 399
  • 2
  • 15
Loading