Minimizing the largest sum

The approximation ratio in this context is the largest sum in the solution returned by the algorithm, divided by the largest sum in the optimal solution (the ratio is larger than 1). Most algorithms below were developed for identical-machines scheduling.

• Greedy number partitioning (also called the Largest Processing Time in the scheduling literature) loops over the numbers, and puts each number in the set whose current sum is smallest. If the numbers are not sorted, then the runtime is ${\displaystyle O(n)}$ and the approximation ratio is at most ${\displaystyle 2-1/k}$. Sorting the numbers increases the runtime to ${\displaystyle O(n\log {n})}$ and improves the approximation ratio to 7/6 when k=2, and ${\displaystyle {\frac {4}{3}}-{\frac {1}{3k}}={\frac {4k-1}{3k}}}$ in general. If the numbers are distributed uniformly in [0,1], then the approximation ratio is at most ${\displaystyle 1+O(\log {\log {n}}/n)}$ almost surely , and ${\displaystyle 1+O(1/n)}$ in expectation.
• Largest Differencing Method (also called the Karmarkar-Karp algorithm ) sorts the numbers in descending order and repeatedly replaces numbers by their differences. The runtime complexity is ${\displaystyle O(n\log {n})}$. In the worst case, its approximation ratio is similar – at most 7/6 for k =2, and at most ${\displaystyle 4/3-1/3k}$ in general. However, in the average case it performs much better than the greedy algorithm: for k =2, when numbers are distributed uniformly in [0,1], its approximation ratio is at most ${\displaystyle 1+1/n^{\Theta (\log {n})}}$ in expectation. It also performs better in simulation experiments.
• The Multifit algorithm uses binary search combined with an algorithm for bin packing . In the worst case, its makespan is at most 8/7 for k =2, and at most 13/11 in general.

Several polynomial-time approximation schemes (PTAS) have been developed:

• Graham^[1]: sec.6 presented the following algorithm. For any integer r>0, choose the r largest numbers in S and partition them optimally. Then allocate the remaining numbers arbitrarily. This algorithm has approximation ratio ${\displaystyle 1+{\frac {1-1/k}{1+\lfloor r/k\rfloor }}}$ and it runs in time ${\displaystyle O(2^{r}n\log {n})}$.
• Sahni^[10] presented a PTAS that attains (1+ε)OPT in time ${\displaystyle O(n\cdot (n^{2}/\epsilon )^{k-1})}$. It is an FPTAS if k is fixed. For k=2, the run-time improves to ${\displaystyle O(n^{2}/\epsilon )}$. The algorithm uses a technique called interval partitioning.
• Hochbaum and Shmoys^[9] presented the following algorithms, which work even when k is part of the input.
  • For any r >0, an algorithm with approximation ratio at most (6/5+2^−r ) in time ${\displaystyle O(n(r+\log {n}))}$.
  • For any r >0, an algorithm with approximation ratio at most (7/6+2^−r ) in time ${\displaystyle O(n(rk^{4}+\log {n}))}$.
  • For any ε>0, an algorithm with approximation ratio at most (1+ε) in time ${\displaystyle O((n/\varepsilon )^{(1/\varepsilon ^{2})})}$ . This is a PTAS.

Maximizing the smallest sum

The approximation ratio in this context is the smallest sum in the solution returned by the algorithm, divided by the smallest sum in the optimal solution (the ratio is less than 1).

• For greedy number partitioning , if the numbers are not sorted then the worst-case approximation ratio is 1/k.^[11] Sorting the numbers increases the approximation ratio to 5/6 when k=2, and ${\displaystyle {\frac {3k-1}{4k-2}}}$ in general, and it is tight.^[12]
• Woeginger^[11] presented a PTAS that attains an approximation factor of ${\displaystyle 1-{\varepsilon }}$ in time ${\displaystyle O(c_{\varepsilon }n\log {k})}$, where ${\displaystyle c_{\varepsilon }}$ a huge constant that is exponential in the required approximation factor ε. The algorithm uses Lenstra's algorithm for integer linear programming.
• The FPTAS of Sahni^[10] works for this objective too.

Maximizing the sum of products

Jin^[13] studies a problem in which the goal is to maximize the sum, over every set i in 1,...,k, of the product of numbers in set i. In a more general variant, each set i may have a weight w_i, and the goal is to maximize the weighted sum of products. This problem has an exact solution that runs in time O(n²).

A PTAS for general objective functions

Let C_i (for i between 1 and k) 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)), or maximize min(f(C_i)), or maximize sum(f(C_i)). Alon, Azar, Woeginger and Yadid^[14] presented general PTAS-s (generalizing the PTAS-s of Sanhi, Hochbaum and Shmoys, and Woeginger) for these four problems. Their algorithm works for any f which 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 (for the minimization problems) or concavity (for the maximization problems).

The runtime of their PTAS-s is linear in n (the number of inputs), but exponential in the approximation precision. The PTAS for minimizing sum(f(C_i)) is based on some combinatorial observations:

1. Let L := the average sum in a single subset (1/k the sum of all inputs). If some input x is at least L, then there is an optimal partition in which one part contains only x. This follows from the convexity of f. Therefore, the input can be pre-processes by assigning each such input to a unique subset. After this preprocessing, one can assume that all inputs are smaller than L.
2. There is an optimal partition in which all subsets sums are strictly betweel L/2 and 2L (L/2 < C_i < 2L for all i in 1,...,k). Particularly, the partition minimizing the sum of squares C_i², among all optimal partitions, satisfies these inequalities.

The PTAS uses an input rounding technique. Given the input sequence S = (v₁,...,v_n) and a positive integer d, the rounded sequence S^#(d) is defined as follows:

• For any v_j > L/d, the sequence S^#(d) contains an input v_j^# which is v_j rounded up to the next integer multiple of L/d². Note that v_j ≤ v_j^# < v_j +L/d², and L/d² < v_j /d, so v_j ^# < (d+1)v_j /d.
• In addition, the sequence S^#(d) contains some inputs equal to L/d. The number of these inputs is determined such that the sum of all these new inputs equals the sum of all inputs in S^#(d) that are at most L/d, rounded up to the next integer multiple of L/d (for example, if the sum of all "short" inputs in S is 51.3L/d, then 52 new L/d inputs are added to S^#(d)).

In S^#(d), all inputs are integer multiples of L/d². Moreover, the above two observations hold for S^#(d) too:

1. Let L^# be the average sum in a single subset (1/k the sum of all inputs in S^#(d)). By construction, L^# is at least L. Since L itself is an integer multiple of L/d², the rounding-up of inputs smaller than L cannot make them larger than L. Therefore, all inputs in S^#(d) are smaller than L, and hence smaller than L^#.
2. There is an optimal partition of S^#(d) in which all subset sums are strictly between L^#/2 and 2L^#. Therefore, all subsets contain at most 2d elements (since all inputs in S^#(d) are at least L/d).

Based on these observations, all inputs in S^#(d) are of the form hL/d², where h is an integer in the range ${\displaystyle (d,d+1,\ldots ,d^{2})}$. Therefore, the input can be represented as an integer vector ${\displaystyle \mathbf {n} =(n_{d},n_{d+1},\ldots ,n_{d^{2}})}$, where ${\displaystyle n_{h}}$ is the number of hL/d² inputs in S^#(d). Moreover, each subset can be represented as an integer vector ${\displaystyle \mathbf {t} =(t_{d},t_{d+1},\ldots ,t_{d^{2}})}$, where ${\displaystyle x_{h}}$ is the number of hL/d² inputs in the subset. The subset sum is then ${\displaystyle C(\mathbf {t} )=\sum _{h=d}^{d^{2}}t_{h}\cdot (hL/d^{2})}$. Denote by ${\displaystyle T}$, the set of vectors ${\displaystyle \mathbf {t} }$ with ${\displaystyle L^{\#}/2<C(\mathbf {t} )<2L^{\#}}$. Since the sum of elements in such a vector is at most 2d, the total number of these elements is smaller than ${\displaystyle {(d^{2})}^{2d}=d^{4d}}$, so ${\displaystyle |T|\leq d^{4d}}$.

There are two different ways to find an optimal solution to S^#(d). One way uses dynamic programming: its run-time is a polynomial whose exponent depends on d. The other way uses Lenstra's algorithm for integer linear programming.

Non-existence of PTAS for some objective functions

In contrast to the above result, if we take f(x) = 2^x, or f(x)=(x-1)², then no PTAS for minimizing sum(f(C_i)) exists unless P=NP.^{[14]: Sec.4} Note that these f(x) are convex, but they do not satisfy Condition F* above. The proof is by reduction from partition problem.

Reduction to bin packing

The bin packing problem has many fast solvers. A BP solver can be used to find an optimal number partitioning.^[25] The idea is to use binary search to find the optimal makespan. To initialize the binary search, we need a lower bound and an upper bound:

• Some lower bounds on the makespan are: (sum S)/k - the average value per subset, s₁ - the largest number in S, and s_k + s_k+1 - the size of a bin in the optimal partition of only the largest k+1 numbers.
• Some upper bounds can be attained by running heuristic algorithms, such as the greedy algorithm or KK.

Given a lower and an upper bound, run the BP solver with bin size middle := (lower+upper)/2.

• If the result contains more than k bins, then the optimal makespan must be larger: set lower to middle and repeat.
• If the result contains at most k bins, then the optimal makespan may be smaller set higher to middle and repeat.