It was first presented by Ronald Graham in 1969 in the context of the identical-machines scheduling problem.
[1]: sec.5 The problem is parametrized by a positive integer k, and called k-way number partitioning.
[2] 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".
[6][7] All these problems are NP-hard,[8] but there are various algorithms that solve it efficiently in many cases.
Some closely-related problems are: There are various algorithms that obtain a guaranteed approximation of the optimal solution in polynomial time.
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).
Several polynomial-time approximation schemes (PTAS) have been developed: 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).
In a more general variant, each set i may have a weight wi, and the goal is to maximize the weighted sum of products.
This problem has an exact solution that runs in time O(n2).
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: 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(Ci)) is based on some combinatorial observations: The PTAS uses an input rounding technique.
Given the input sequence S = (v1,...,vn) and a positive integer d, the rounded sequence S#(d) is defined as follows: In S#(d), all inputs are integer multiples of L/d2.
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.
as the optimal (minimum) value of the objective function sum(f(Ci)), when the input vector is
It is linear in n for any fixed d. For each vector t in T, introduce a variable xt denoting the number of subsets with this configuration.
Minimizing sum(f(Ci)) can be attained by the solving the following ILP: The number of variables is at most
), but polynomial in the binary representation of the coefficients, which are in O(log(n)).
The following lemmas relate the partitions of the rounded instance S#(d) and the original instance S. Given a desired approximation precision ε>0, let δ>0 be the constant corresponding to ε/3, whose existence is guaranteed by Condition F*.
It is possible to show that converted partition of S has a total cost of at most
In contrast to the above result, if we take f(x) = 2x, or f(x)=(x-1)2, then no PTAS for minimizing sum(f(Ci)) exists unless P=NP.
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 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: Given a lower and an upper bound, run the BP solver with bin size middle := (lower+upper)/2.
In the balanced number partitioning problem, there are constraints on the number of items that can be allocated to each subset (these are called cardinality constraints).
[26] One application of the partition problem is for manipulation of elections.
For k=2, the same is true for any other voting rule that is based on scoring.