Balanced number partitioning

Balanced number partitioning is a variant of multiway number partitioning in which there are constraints on the number of items allocated to each set. The input to the problem is a set of n items of different sizes, and two integers k, c. The output is a partition of the items into k subsets, such that the number of items in each subset is at most c. Subject to this, it is required that the sums of sizes in the k subsets are as similar as possible. The problem has applications, for example, in manufacturing of VLSI chips, and in assigning tools to machines in flexible manufacturing systems.

Two-way balanced partitioning

A common special case is when there are two sets (k=2). The goal is to partition the n items into two subsets of floor(n/2) and ceiling(n/2) items. It is a variant of the partition problem. It is NP-hard to decide whether there exists a partition in which the sums in the two subsets are equal; see problem [SP12]. There are many algorithms that aim to find a balanced partition in which the sum is as nearly-equal as possible.

• Coffman, Frederickson and Lueker present a restricted version of the LPT algorithm (called RLPT), in which inputs are assigned in pairs. When inputs are uniformly-distributed random variables, the expected largest sum of RLPT is exactly ${\frac {n}{4}}+{\frac {1}{2n+2}}$. The expected work-difference (difference between largest and smallest sum) is $\Theta (1/n)$.
• Lueker presents a variant of the LDM algorithm (called Pairwise Differencing Method or PDM). Its expected work-difference is $\Theta (1/n)$.
• Tsai presents an algorithm called Restricted Largest Difference (RLD). Its work-difference is $O(\log {n}/n^{2})$ almost surely.
• Yakir presents a balanced variant of the LDM algorithm for k=2, called BLDM. Its expected work-difference is $n^{-\Theta (\log n)}$.
• Mertens presents a complete anytime algorithm for balanced two-way partitioning. It combines the BLDM algorithm with the complete-Karmarkar-Karp algorithm.

Balanced triplet partitioning

Another special case is when the number of items in each subset should be at most 3 (c=3). Deciding whether there exists such a partition with equal sums is the 3-partition problem, which is known to be strongly NP-hard. There are approximation algorithms that aim to find a partition in which the sum is as nearly-equal as possible.

• Kellerer and Woeginger adapt the LPT algorithm to triplet partitioning (where there are at most 3*k items, and each subset should contain at most 3 items). Their algorithm is called modified-LPT or MLPT. It orders the 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 ${\frac {4k-1}{3k}}$ of the minimum largest sum, which is the same approximation ratio that LPT attains for the unconstrained problem. The bound is tight for MLPT.
• Chen, He and Lin show that, for the same problem, MLPT attains at least ${\frac {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.

General cardinality constraints

A more general case is when the number of items in each subset should be at most c, where c can be any positive integer.

• 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 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 (a combination of LPT and MultiFit): approximation ratio at most $4/3$. It is not known if this is tight.
  • The also conjecture that Modified-LPT has an approximation ratio ${\frac {4k-1}{3k}}$ . Currently, this conjecture is known to be true only for c=3.
• Michiels, Korst, Aarts, van Leeuwen and Spieksma study a variant in which each of the k sets must contain either ceiling(n/k) or floor(n/k) items (so c=ceiling(n/k)). They prove that the approximation ratio of Balanced-LDM (BLDM), for the minimum largest sum, is exactly 4/3 for c=3, 19/12 for c=4, 103/60 for c=5, 643/360 for c=6, and 4603/2520 for c=7. The ratios were found by solving a mixed integer linear program. In general (for any c), the approximation ratio is at least $2-\sum _{j=0}^{c-1}{\frac {j!}{c!}}$ and at most $2-{\frac {1}{c-1}}$. When the parameter is the number of subsets (k), the approximation ratio is exactly $2-{\frac {1}{k}}$.
• When c is fixed, a PTAS of Hochbaum and Shmoys can be used for balanced partitioning. When c is part of the input, no PTAS is currently known.

Kernel balanced partitioning

The kernel balanced-partitioning problem is a variant of balanced partitioning in which some k pre-specified items are kernels, and each of the k subsets must contain a single kernel.

• Chen, He and Yao prove that the problem is NP-hard even for c=3 (for c=2 it can be solved efficiently by finding a maximum weight matching). They then present an algorithm called Kernel-LPT (KLPT): it assigns a kernel to each subset, and then runs the modified LPT algorithm (puts each item into the subset with the smallest sum among those that have fewer than c items). They prove that, with c=3, KLPT has an approximation ratio ${\frac {4k-1}{3k}}$ for the minimum largest sum. However, Chen, He and Lin claim that its tight approximation ratio is ${\frac {3k-1}{2k}}$ for the minimum largest sum, and ${\frac {2k-1}{3k-2}}$ for the maximum smallest sum.

Relations between balanced and unconstrained problems

There are some general relations between approximations to the balanced partition problem and the standard (unconstrained) partition problem.

• Babel, Kellerer and Kotov prove that the ratio between the unconstrained optimum and the constrained optimum is at most $2-{\frac {2}{k}}$, and it is tight.
• Kellerer and Kotov prove that every heuristic for balanced partitioning with capacity c and approximation-ratio r (for the minimum largest sum) can be employed to obtain a heuristic for unconstrained partitioning with approximation-ratio $\max \left(r,{\frac {c+2}{c+1}}-{\frac {1}{k(c+1)}}\right)$. In particular, their $7/6$-approximation algorithm for triplet partitioning (c=3) can be used to obtain a heuristic for unconstrained partitioning with approximation-ratio $\max \left({\frac {7}{6}},{\frac {5}{4}}-{\frac {1}{4k}}\right)$.

Matroid constraints

The cardinality constraints can be generalized to matroid constraints. A fixed matroid is given as a parameter, and each of the k subsets should be an independent set or a base of this matroid. Cardinality constraints are special cases of matroid constraints in which the matroid is a uniform matroid. Cardinality+kernel constraints are a special case in which the matroid is a partition matroid.

• Burkard and Yao derive conditions for cases in which the problem can be solved optimally by a greedy algorithm.