Worst-case maximum sum

In the worst case, the largest sum in the greedy partition is at most ${\displaystyle {\frac {4}{3}}}$ times the optimal (minimum) largest sum.^{[2][lower-alpha 1]}

A more detailed analysis yields a factor of ${\displaystyle {\frac {4m-1}{3m}}={\frac {4}{3}}-{\frac {1}{3m}}}$ times the optimal (minimum) largest sum.^[1][3] (for example, when m =2 this ratio is ${\displaystyle 7/6\approx 1.167}$).^{[lower-alpha 2]}

The factor ${\displaystyle {\frac {4m-1}{3m}}}$ is tight. Suppose there are ${\displaystyle 2m+1}$ inputs (where m is even): ${\displaystyle 2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m}$. Then the greedy algorithm returns:

• ${\displaystyle 2m-1,m,m}$
• ${\displaystyle 2m-1,m}$
• ${\displaystyle 2m-2,m+1}$
• ${\displaystyle 2m-2,m+1}$,
• ...
• ${\displaystyle 3m/2,3m/2-1}$
• ${\displaystyle 3m/2,3m/2-1}$

with a maximum of ${\displaystyle 4m-1}$, but the optimal partition is:

• ${\displaystyle m,m,m}$
• ${\displaystyle 2m-1,m+1}$
• ${\displaystyle 2m-1,m+1}$
• ${\displaystyle 2m-2,m+2}$
• ${\displaystyle 2m-2,m+2}$
• ...
• ${\displaystyle 3m/2,3m/2}$

with a maximum of ${\displaystyle 3m}$.

Worst-case minimum sum

In the worst case, the smallest sum in the returned partition is at least ${\displaystyle {\frac {3}{4}}}$ times the optimal (maximum) smallest sum.^[5]

Average-case maximum sum

In the average case, if the input numbers are distributed uniformly in [0,1], then the largest sum in an LPT schedule satisfies the following properties:

• The expected largest sum for m=2 machines is at least ${\displaystyle {\frac {n}{4}}+{\frac {1}{4n+4}}}$ and at most ${\displaystyle {\frac {n}{4}}+{\frac {e}{2n+2}}}$, where n is the number of inputs.^[9]
• The largest sum is at most ${\displaystyle 1+O(\log {\log {n}}/n)}$ times the optimum almost surely, and ${\displaystyle 1+O(1/n)}$ in expectation, where ${\displaystyle n}$ is the number of inputs.^[10]
• The difference between the LPT largest sum and the optimal largest sum is at most ${\displaystyle O(\log {n}/n)}$ almost surely (for uniform or negative exponential distributions), and at most ${\displaystyle O(m^{2}/n)}$ in expectation (for uniform distribution). These results hold also for machines with different speeds.^[11]

General objectives

Let C_i (for i between 1 and m) be the sum of subset i in a given partition. Instead of minimizing the objective function max(C_i), one can minimize the objective function max(f(C_i)), where f is any fixed function. Similarly, one can minimize the objective function sum(f(C_i)). Alon, Azar, Woeginger and Yadid^[12] prove that, if f satisfies the following two conditions:

1. A strong continuity condition called Condition F*: for every ε>0 there exists δ>0 such that, if |y-x|<δx, then |f(y)-f(x)|<εf(x).
2. Convexity.

Then the LPT rule has a finite approximation ratio for minimizing sum(f(C_i)).

Uniform machines

In uniform-machines scheduling, different machines may have different speeds. The LPT rule assigns each job to the machine on which its completion time will be earliest (that is, LPT may assign a job to a machine with a larger current load, if this machine is so fast that it would finish that job earlier than all other machines).^[13]

• Gonzalez, Ibarra and Sahni^[13] show that the approximation ratio of LPT with m uniform machines is at most ${\displaystyle 2m/(m+1)}$. It is not tight, but there is an asymptotic lower bound of 1.5 when m approaches infinity. For the special case of m=2 machines, the approximation ratio is at most ${\displaystyle (1+{\sqrt {17}})/4\approx 1.281}$ and it is tight.
• Mireault, Orlin and Vohra^[14] study a setting with two machines, in which one machine is q times faster than the other. They compute the approximation ratio of LPT as a function of q. When q=1, their result coincides with the 7/6 factor known for identical machines.
• Koulamas and Kyparisis^[15] present a modification of LPT in which the three longest jobs are scheduled optimally, and the remaining jobs are scheduled based on the LPT rule. The approximation ratio for two machines is ${\displaystyle {\sqrt {1.5}}\approx 1.2247}$ and it is tight.

Cardinality constraints

In the balanced partition problem, there are constraints on the number of jobs that can be assigned to each machine. A simple constraint is that each machine can process at most c jobs. The LPT rule assigns each job to the machine with the smallest load from among those with fewer than c jobs. This rule is called modified LPT or MLPT.

• Kellerer and Woeginger^[16] study a variant in which there are at most 3*m jobs, and each machine must contain at most 3 jobs (this can be seen as a generalization of 3-partition problem). They show that MLPT attains at most ${\displaystyle (4m-1)/(3m)}$ of the minimum largest sum, which the same approximation ratio that LPT attains for the unconstrained problem. The bound is tight for MLPT. It is conjectured^[17] that MLPT has the same approximation ratio for more general cardinality constraints (c>3). Currently, it is known that the approximation ratio of MLPT for general c>3 is at most 2.^[18]
• Chen, He and Lin^[19] show that, for the same problem, MLPT attains at least ${\displaystyle (3m-1)/(4m-2)}$ of the maximum smallest sum, which is again the same ratio that LPT attains for the unconstrained problem.

Another constraint is that the number of jobs on all machines should be ${\displaystyle n/m}$ rounded either up or down. In an adaptation of LPT called restricted LPT or RLPT, inputs are assigned in pairs - one to each machine (for m=2 machines).^[9] The resulting partition is balanced by design.

• Coffman, Frederickson and Lueker^[9] show that the expected largest sum of RLPT when inputs are uniformly-distributed random variables is exactly ${\displaystyle {\frac {n}{4}}+{\frac {1}{2n+2}}}$. The expected difference between the largest and smallest sum is ${\displaystyle \Theta (1/n)}$.^[20]

Kernel constraints - non-simultaneous availability

In the kernel partitioning problem, there are some m pre-specified jobs called kernels, and each kernel must be scheduled to a unique machine. An equivalent problem is scheduling when machines are available in different times: each machine i becomes available at some time t_i ≥ 0 (the time t_i can be thought of as the length of the kernel job).

A simple heuristic algorithm, called SLPT,^[21] assigns each kernel to a different subset, and then runs the LPT algorithm.

• Lee^[22] proves that this heuristic has a tight approximation ratio ${\displaystyle {\frac {3m-1}{2m}}}$ for the minimum largest sum. He then suggests running, in the second step, a modified version of LPT, and proves that it attains an approximation ratio ${\displaystyle {\frac {4}{3}}}$ .
• Lin, Yao and He^[23] prove that this heuristic has a tight approximation ratio ${\displaystyle {\frac {2m-1}{3m-2}}}$ for the maximum smallest sum.
• Shen, Wang and Wang^[24] study different objective functions for this setting, and present polynomial-time algorithms.

Online settings

Often, the inputs come online, and their sizes becomes known only when they arrive. In this case, it is not possible to sort them in advance. List scheduling is a similar algorithm that takes a list in any order, not necessarily sorted. Its approximation ratio is ${\displaystyle {\frac {2m-1}{m}}=2-{\frac {1}{m}}}$.

A more sophisticated adaptation of LPT to an online setting attains an approximation ratio of 3/2.^[25]