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 m, k. The output is a partition of the items into m subsets, such that the number of items in each subset is at most k. Subject to this, it is required that the sums of sizes in the m subsets are as similar as possible.

An example application is identical-machines scheduling where each machine has a job-queue that can hold at most k jobs. The problem has applications also in manufacturing of VLSI chips, and in assigning tools to machines in flexible manufacturing systems.

In the standard three-field notation for optimal job scheduling problems, the problem of minimizing the largest sum is sometimes denoted by "P | # ≤ k | Cmax". The middle field "# ≤ k" denotes that the number of jobs in each machine should be at most k. This is in contrast to the unconstrained version, which is denoted by "P∥Cmax".

Two-way balanced partitioning

A common special case called two-way balanced partitioning is when there should be two subsets (m = 2). The two subsets should contain 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.

Balanced triplet partitioning

Another special case called 3-partitioning is when the number of items in each subset should be at most 3 (k = 3). Deciding whether there exists such a partition with equal sums is exactly 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.

Balanced partitioning with larger cardinalities

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

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−2m, and it is tight.
  • Kellerer and Kotov prove that every heuristic for balanced partitioning with capacity k and approximation-ratio r (for the minimum largest sum) can be employed to obtain a heuristic for unconstrained partitioning with approximation-ratio max⁡(r,k+2k+1−1m(k+1)). In particular, their 7/6-approximation algorithm for triplet partitioning (k = 3) can be used to obtain a heuristic for unconstrained partitioning with approximation-ratio max⁡(76,54−14m).

Different cardinality constraints

The cardinality constraints can be generalized by allowing a different constraint on each subset. This variant is introduced in the "open problems" section of, who call the ki-partitioning problem. He, Tan, Zhu and Yao present an algorithm called HARMONIC2 for maximizing the smallest sum with different cardinality constraints. They prove that its worst-case ratio is at least max⁡(1km,k1km1⌈∑i=1m1i⌉+1).

Categorized cardinality constraints

Another generalization of cardinality constraints is as follows. The input items are partitioned into k categories. For each category h, there is a capacity constraint kh. Each of the m subsets may contain at most kh items from category h. In other words: all m subsets should be independent set of a particular partition matroid. Two special cases of this problem have been studied.

Kernel partitioning

In the kernel balanced-partitioning problem, some m pre-specified items are kernels, and each of the m subsets must contain a single kernel (and an unlimited number of non-kernels). Here, there are two categories: the kernel category with capacity 1, and the non-kernel category with unlimited capacity.

  • Chen, He and Yao prove that the problem is NP-hard even for k = 3 (for k = 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 k items). They prove that, with k = 3, KLPT has an approximation ratio 4m−13m for the minimum largest sum.: 3  However, Chen, He and Lin: 2  claim that its tight approximation ratio is 3m−12m for the minimum largest sum,[clarification needed] and 2m−13m−2 for the maximum smallest sum.

One-per-category partitioning

In another variant of this problem, there are some k categories of size m, and each subset should contain exactly one item from each category. That is, kh = 1 for each category h.

  • Wu and Yao presented the layered LPT algorithm – a variant of the LPT algorithm. They prove that its approximation ratio is 2−1m for minimizing the largest sum; 1m for maximizing the smallest sum in the general case; and in some special cases, can be improved to m2m−1 for general k and m−12m−3 for k = 3.
  • Li and Li presented different algorithms for the same problem. For minimizing the largest sum, they present an EPTAS for constant k, and FPTAS for constant m. For maximizing the smallest sum, they present a 1/(k − 1) approximation algorithm for the general case, and an EPTAS for constant k. They also study a more general objective: minimizing the lp-norm of the vector of sums. They prove that the layered-LPT algorithm is a 2-approximation algorithm for all norms.
  • Dell'Olmo, Hansen, Pallottino and Storchi study 32 different objectives for this problem. For each of the four operators max, min, sum, diff, one operator can be applied to the k items inside each subset, and then one operator can be applied to the m results for the different subsets. Each of these 16 objectives can be either maximized or minimized, for a total of 32. They show that 21 of these problems can be solved in linear time; 7 require more complex, but still polynomial-time, algorithms; 3 are NP-hard: maximizing (min, sum), minimizing (max, sum) and minimizing (diff, sum). They left open the status of minimizing (diff, diff).

See also

Matroid-constrained number partitioning is a generalization in which a fixed matroid is given as a parameter, and each of the m subsets should be an independent set or a base of this matroid.