Multiway number partitioning

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 more than 1).

• Greedy number partitioning (also called the Largest Processing Time method) 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 O(n) and the approximation ratio is at most ${\displaystyle 2-1/k}$. Sorting the numbers increases the runtime to O(n log n ) and improves the approximation ratio to 7/6 when k=2, and ${\displaystyle 4/3+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 complextiy is 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[9]^: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})}$.
• Sanhi[10] presented a PTAS for the case where k is not part of the input.
• Hochbaum and Shmoys[11] 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})})}$ .
• There are variations of this idea that are fully polynomial-time approximation schemes for the subset-sum problem, and hence for the partition problem as well. [12]

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.[5] 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.[13]

• Woeginger[5] 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.

Let s_i (for i between 1 and k) be the sum of subset i in a given partition. Instead of minimizing the objective function max(s_i), one can minimize the objective function max(f(s_i)), where f is any fixed function. Similarly, one can minimize the objective function sum(f(s_i)), or maximize min(f(s_i)), or maximize sum(f(s_i)). Alon, Azar, Woeginger and Yadid[14] presented a general PTAS, that works for any f which satisfies a certain continuity condition, and is convex (for the minimization problems) or concave (for the maximization problems). Their algorithm generalizes the PTAS-s of Sanhi, Hochbaum and Shmoys, and Woeginger. The runtime of their PTAS is linear in n, but exponential in the approximation precision. They show that, for some functions f that do not satisfy these conditions, no PTAS exists unless P=NP.

The bin packing problem has many fast solvers. A BP solver can be used to find an optimal number partitioning.[22] 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.