Multiway number partitioning

In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in the context of the Identical-machines scheduling problem. The problem is parametrized by a positive integer k, and called k-way number partitioning. The input to the problem is a multiset S of numbers (usually integers), whose sum is k*T.

The associated decision problem is to decide whether S can be partitioned into k subsets such that the sum of each subset is exactly T. There is also an optimization problem: find a partition of S into k subsets, such that the k sums are "as near as possible". The exact optimization objective can be defined in several ways:

• Minimize the difference between the largest sum and the smallest sum. This objective is common in papers about multiway number partitioning, as well as papers originating from physics applications.
• Minimize the largest sum. This objective is equivalent to one objective for Identical-machines scheduling. There are k identical processors, and each number in S represents the time required to complete a single-processor job. The goal is to partition the jobs among the processors such that the makespan (the finish time of the last job) is minimized.
• Maximize the smallest sum. This objective corresponds to the application of fair item allocation, particularly the maximin share. It also appears in voting manipulation problems, and in sequencing of maintenance actions for modular gas turbine aircraft engines. Suppose there are some k engines, which must be kept working for as long as possible. An engine needs a certain critical part in order to operate. There is a set S of parts, each of which has a different lifetime. The goal is to assign the parts to the engines, such that the shortest engine lifetime is as large as possible.

These three objective functions are equivalent when k=2, but they are all different when k≥3.

All these problems are NP-hard, but there are various algorithms that solve it efficiently in many cases.

Some closely-related problems are:

• The partition problem - a special case of multiway number partitioning in which the number of subsets is 2.
• The 3-partition problem - a different and harder problem, in which the number of subsets is not considered a fixed parameter, but is determined by the input (the number of sets is the number of integers divided by 3).
• The bin packing problem - a dual problem in which the total sum in each subset is bounded, but k is flexible; the goal is to find a partition with the smallest possible k. The optimization objectives are closely related: the optimal number of d-sized bins is at most k, iff the optimal size of a largest subset in a k-partition is at most d.
• The uniform-machines scheduling problem - a more general problem in which different processors may have different speeds.

Approximation algorithms

There are various algorithms that obtain a guaranteed approximation of the optimal solution in polynomial time. There are different approximation algorithms for different objectives.

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 $O(n)$ and the approximation ratio is at most $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 ${\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 $1+O(\log {\log {n}}/n)$ almost surely , and $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 $O(n\log {n})$. In the worst case, its approximation ratio is similar - at most 7/6 for k =2, and at most $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 $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 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 $1+{\frac {1-1/k}{1+\lfloor r/k\rfloor }}$ and it runs in time $O(2^{r}n\log {n})$.
• Sahni presented a PTAS that attains (1+ε)OPT in time $O(n\cdot (n^{2}/\epsilon )^{k-1})$. It is an FPTAS if k is fixed. For k=2, the run-time improves to $O(n^{2}/\epsilon )$. The algorithm uses a technique called interval partitioning.
• Hochbaum and Shmoys 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 $O(n(r+\log {n}))$.
  • For any r >0, an algorithm with approximation ratio at most (7/6+2^−r ) in time $O(n(rk^{4}+\log {n}))$.
  • For any ε>0, an algorithm with approximation ratio at most (1+ε) in time $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. Sorting the numbers increases the approximation ratio to 5/6 when k=2, and ${\frac {3k-1}{4k-2}}$ in general, and it is tight.
• Woeginger presented a PTAS that attains an approximation factor of $1-{\varepsilon }$ in time $O(c_{\varepsilon }n\log {k})$, where $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 works for this objective too.

Other objective functions

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

Cardinality constraints

In the balanced number partitioning problem, the cardinality of each subset must be either floor(n/k) or ceiling(n/k), i.e., the cardinality of all subsets must be the same up to 1. This is important, for example, in manufacturing of VLSI chips, and in assigning tools to machines in flexible manufacturing systems.

• Frenk and Rinnooy Kan prove that the difference between the LPT largest sum and the optimal largest sum is at most $O(\log {n}/n)$ almost surely (for uniform or negative exponential distributions), and at most $O(k^{2}/n)$ in expectation (for uniform distribution).
• Karmarkar and Karp developed the Largest differencing method (LDM), and proved that, for k=2, its work-difference (the difference between largest and smallest sum) is $n^{-\Theta (\log n)}$almost surely when the distribution is smooth.
• Yakir presents another algorithm for balanced partitioning with the same rate of convergence to zero, $n^{-\Theta (\log n)}$.
• Lueker presented the Pairing-differencing-method (PDM), a simpler variant of LDM. He proved that, for k=2, its work-difference is $\Theta (1/n)$.
• Coffman, Frederickson and Lueker show that a restricted version of the LPT algorithm (called RLPT or RLF), in which inputs are assigned in pairs, attains a work-difference of $\Theta (1/n)$.
• Tsai presents an algorithm called Restricted Largest Difference (RLD), attaining a work-difference of $O(\log {n}/n^{2})$ almost surely when inputs are independent uniform random variables. The algorithm also minimizes the total flow time.

There are variants of multiway number partitioning in which there are cardinality constraints on the sets.

• Kellerer and Woeginger study a variant in which there are at most 3*k items, and each set must contain at most 3 items (a generalization of 3-partition problem). They adapt the LPT algorithm to this setting: their algorithm (called modified-LPT or MLPT) orders the input items from large to small, and puts each item in turn into the bin with the smallest sum among those bins that contain fewer than 3 items. They show that the MLPT algorithm attains at most $(4k-1)/(3k)$ 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 that MLPT has the same approximation ratio for more general cardinality constraints.
• Chen, He and Lin show that, for the same problem, MLPT attains at least $(3k-1)/(4k-2)$ of the maximum smallest sum, which is again the same ratio that LPT attains for the unconstrained problem.
• Kellerer and Kotov present a different algorithm (for the case with exactly 3*k items), that attains at most $7/6$ of the minimum largest sum.
• Babel, Kellerer and Kotov study a variant in which there are c*k items (for some integer c), and each of the k sets must contain exactly c items. They prove that the ratio between the unconstrained optimum and the constrained optimum is at most $2-{\frac {2}{k}}$, and it is tight. They also present several heuristic algorithms for approximating the minimum largest sum.
  • Folding algorithm: optimal for k=2, and in general has tight approximation ratio $2-{\frac {1}{k}}$.
  • Exchange algorithm: tight approximation ratio $2-{\frac {2}{k+1}}$. It is not known if it runs in polynomial time.
  • Primal-dual algorithm (similar to MultiFit): approximation ratio at most $4/3$. It is not known if this is tight.

Exact algorithms

There are exact algorithms, that always find the optimal partition. Since the problem is NP-hard, such algorithms might take exponential time in general, but may be practically usable in certain cases.

• The pseudopolynomial time number partitioning takes O(n(k − 1)m^{k − 1}) memory, where m is the largest number in the input. It is practical only when k=2, or when k=3 and the inputs are small integers.
• The Complete Greedy Algorithm (CGA) considers all partitions by constructing a k-ary tree. Each level in the tree corresponds to an input number, where the root corresponds to the largest number, the level below to the next-largest number, etc. Each of the k branches corresponds to a different set in which the current number can be put. Traversing the tree in depth-first order requires only O(n) space, but might take O(kⁿ) time. The runtime can be improved by using a greedy heuristic: in each level, develop first the branch in which the current number is put in the set with the smallest sum. This algorithm finds first the solution found by greedy number partitioning, but then proceeds to look for better solutions.
• The Complete Karmarkar-Karp algorithm (CKK) considers all partitions by constructing a tree of degree $k!$ . Each level corresponds to a pair of k-tuples, and each of the $k!$ branches corresponds to a different way of combining these k-tuples. This algorithm finds first the solution found by the largest differencing method, but then proceeds to find better solutions. For k =2 and k =3, CKK runs substantially faster than CGA on random instances. The advantage of CKK over CGA is much larger in the latter case (when an equal partition exists), and can be of several orders of magnitude. In practice, with k=2, problems of arbitrary size can be solved by CKK if the numbers have at most 12 significant digit s; with k=3, at most 6 significant digits. CKK can also run as an anytime algorithm : it finds the KK solution first, and then finds progressively better solutions as time allows (possibly requiring exponential time to reach optimality, for the worst instances). For k ≥ 4, CKK becomes much slower, and CGA performs better.
• Recursive Number Partitioning (RNP) uses CKK for k=2, but for k>2 it recursively splits S into subsets and splits k into halves. It performs much better than CKK.
• Korf, Schreiber and Moffitt presented hybrid algorithms, combining CKK, CGA and other methods from the subset sum problem and the bin packing problem to achieve an even better performance.

Reduction to bin packing

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

Variants

A recent variant is the multidimensional multiway number partitioning.

Applications

One application of the partition problem is for manipulation of elections. Suppose there are three candidates (A, B and C). A single candidate should be elected using the veto voting rule, i.e., each voter vetos a single candidate and the candidate with the fewest vetos wins. If a coalition wants to ensure that C is elected, they should partition their vetoes among A and B so as to maximize the smallest number of vetoes each of them gets. If the votes are weighted, then the problem can be reduced to the partition problem, and thus it can be solved efficiently using CKK. For k=2, the same is true for any other voting rule that is based on scoring. However, for k>2 and other voting rules, some other techniques are required.