Hubbry Logo
Partition problemPartition problemMain
Open search
Partition problem
Community hub
Partition problem
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Partition problem
Partition problem
Partition problem
View on Wikipedia
from Wikipedia

In number theory and computer science, the partition problem, or number partitioning,[1] is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest hard problem".[2][3]

There is an optimization version of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized. The optimization version is NP-hard, but can be solved efficiently in practice.[4]

The partition problem is a special case of two related problems:

  • In the subset sum problem, the goal is to find a subset of S whose sum is a certain target number T given as input (the partition problem is the special case in which T is half the sum of S).
  • In multiway number partitioning, there is an integer parameter k, and the goal is to decide whether S can be partitioned into k subsets of equal sum (the partition problem is the special case in which k = 2).

However, it is quite different to the 3-partition problem: in that problem, the number of subsets is not fixed in advance – it should be |S|/3, where each subset must have exactly 3 elements. 3-partition is much harder than partition – it has no pseudo-polynomial time algorithm unless P = NP.[5]

Examples

[edit]

Given S = {3,1,1,2,2,1}, a valid solution to the partition problem is the two sets S1 = {1,1,1,2} and S2 = {2,3}. Both sets sum to 5, and they partition S. This solution is not unique. S1 = {3,1,1} and S2 = {2,2,1} is another solution.

Not every multiset of positive integers has a partition into two subsets with equal sum. An example of such a set is S = {2,5}.

Computational hardness

[edit]

The partition problem is NP hard. This can be proved by reduction from the subset sum problem.[6] An instance of SubsetSum consists of a set S of positive integers and a target sum T; the goal is to decide if there is a subset of S with sum exactly T.

Given such an instance, construct an instance of Partition in which the input set contains the original set plus two elements: z1 and z2, with z1 = sum(S) and z2 = 2T. The sum of this input set is sum(S) + z1 + z2 = 2 sum(S) + 2T, so the target sum for Partition is sum(S) + T.

  • Suppose there exists a solution S′ to the SubsetSum instance. Then sum(S′) = T, so sum(S′ ∪ z2) = sum(S) + T, so S′ ∪ z1 is a solution to the Partition instance.
  • Conversely, suppose there exists a solution S′′ to the Partition instance. Then, S′′ must contain either z1 or z2, but not both, since their sum is more than sum(S) + T. If S'' contains z1, then it must contain elements from S with a sum of exactly T, so S'' minus z1 is a solution to the SubsetSum instance. If S'' contains z2, then it must contain elements from S with a sum of exactly sum(S) − T, so the other objects in S are a solution to the SubsetSum instance.

Approximation algorithms

[edit]

As mentioned above, the partition problem is a special case of multiway-partitioning and of subset-sum. Therefore, it can be solved by algorithms developed for each of these problems. Algorithms developed for multiway number partitioning include:

  • Greedy number partitioning – 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 3/2 ("approximation ratio" means the larger sum in the algorithm output, divided by the larger sum in an optimal partition). Sorting the numbers increases the runtime to O(n log n) and improves the approximation ratio to 7/6. If the numbers are distributed uniformly in [0,1], then the approximation ratio is at most almost surely, and 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. However, in the average case it performs much better than the greedy algorithm: when numbers are distributed uniformly in [0,1], its approximation ratio is at most 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 approximation ratio is 8/7.
  • The subset sum problem has an FPTAS which can be used for the partition problem as well, by setting the target sum to sum(S)/2.

Exact algorithms

[edit]

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. Algorithms developed for multiway number partitioning include:

  • The pseudopolynomial time number partitioning takes time and needs memory, where m is the largest number in the input.
  • The Complete Greedy Algorithm (CGA) considers all partitions by constructing a binary 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 branch corresponds to a different set in which the current number can be put. Traversing the tree in depth-first order requires only space, but might take 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. Some variations of this idea are fully polynomial-time approximation schemes for the subset-sum problem, and hence for the partition problem as well.[7][8]
  • The Complete Karmarkar–Karp algorithm (CKK) considers all partitions by constructing a binary tree. Each level corresponds to a pair of numbers. The left branch corresponds to putting them in different subsets (i.e., replacing them by their difference), and the right branch corresponds to putting them in the same subset (i.e., replacing them by their sum). This algorithm finds first the solution found by the largest differencing method, but then proceeds to find better solutions. It runs substantially faster than CGA on random instances. Its advantage is much larger when an equal partition exists, and can be of several orders of magnitude. In practice, problems of arbitrary size can be solved by CKK if the numbers have at most 12 significant digits.[9] 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).[1] It requires space, but in the worst case might take time.

Algorithms developed for subset sum include:

  • Horowitz and Sanhi – runs in time , but requires space.
  • Schroeppel and Shamir – runs in time , and requires much less space – .
  • Howgrave-Graham and Joux – runs in time , but it is a randomized algorithm that only solves the decision problem (not the optimization problem).

Hard instances and phase-transition

[edit]

Sets with only one, or no partitions tend to be hardest (or most expensive) to solve compared to their input sizes. When the values are small compared to the size of the set, perfect partitions are more likely. The problem is known to undergo a "phase transition"; being likely for some sets and unlikely for others. If m is the number of bits needed to express any number in the set and n is the size of the set then tends to have many solutions and tends to have few or no solutions. As n and m get larger, the probability of a perfect partition goes to 1 or 0 respectively. This was originally argued based on empirical evidence by Gent and Walsh,[10] then using methods from statistical physics by Mertens,[11][12] and later proved by Borgs, Chayes, and Pittel.[13]

Probabilistic version

[edit]

A related problem, somewhat similar to the Birthday paradox, is that of determining the size of the input set so that we have a probability of one half that there is a solution, under the assumption that each element in the set is randomly selected with uniform distribution between 1 and some given value. The solution to this problem can be counter-intuitive, like the birthday paradox.

Variants and generalizations

[edit]

Equal-cardinality partition is a variant in which both parts should have an equal number of items, in addition to having an equal sum. This variant is NP-hard too.[5]: SP12  Proof. Given a standard Partition instance with some n numbers, construct an Equal-Cardinality-Partition instance by adding n zeros. Clearly, the new instance has an equal-cardinality equal-sum partition iff the original instance has an equal-sum partition. See also Balanced number partitioning.

Product partition is the problem of partitioning a set of integers into two sets with the same product (rather than the same sum). This problem is strongly NP-hard.[14]

Kovalyov and Pesch[15] discuss a generic approach to proving NP-hardness of partition-type problems.

Applications

[edit]

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 a voting rule based on scoring, e.g. the veto rule (each voter vetoes a single candidate and the candidate with the fewest vetoes wins). If a coalition wants to ensure that C is elected, they should partition their votes 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. The same is true for any other voting rule that is based on scoring.[16]

Notes

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Partition problem

View on Grokipedia
from Grokipedia
The partition problem is a decision problem in computer science and mathematics that asks whether a given multiset of positive integers can be partitioned into two disjoint subsets with equal sums. Formally, for a multiset S={s1,s2,…,sn}S = \{s_1, s_2, \dots, s_n\} where each si>0s_i > 0, the question is whether there exists a subset S1⊆SS_1 \subseteq S such that ∑s∈S1s=∑s∈S∖S1s=12∑s∈Ss\sum_{s \in S_1} s = \sum_{s \in S \setminus S_1} s = \frac{1}{2} \sum_{s \in S} s, which requires the total sum to be even. This problem is one of the 21 canonical NP-complete problems identified by Richard M. Karp in 1972, establishing its computational intractability: while solutions can be verified in polynomial time, no known polynomial-time algorithm exists for solving it in the general case unless P = NP. Despite its hardness, the partition problem admits a exact using dynamic programming, with O(n⋅T/2)O(n \cdot T/2) where TT is the total sum of the elements, making it weakly NP-complete rather than strongly NP-complete. Brute-force enumeration of subsets yields an exact solution in O(2n)O(2^n) time, but practical instances often rely on for the optimization variant, which seeks to minimize the between subset sums rather than requiring exact equality. Notable methods include the Karmarkar–Karp differencing , a that iteratively pairs the largest remaining numbers and replaces them with their difference, producing partitions with differences exponentially smaller than the input sum in typical cases. The problem underpins applications in , such as load balancing in multiprocessor scheduling, and serves as a foundational example in complexity theory for reductions to other NP-hard problems like subset sum and knapsack.

Problem Definition and Formulation

Formal Statement

The partition problem is a classic in . Given a S={s1,s2,…,sn}S = \{s_1, s_2, \dots, s_n\} of nn positive integers, the task is to determine whether there exists a S1⊆SS_1 \subseteq S such that ∑s∈S1s=∑s∈S∖S1s\sum_{s \in S_1} s = \sum_{s \in S \setminus S_1} s. This equality holds if and only if the total sum Σ=∑s∈Ss\Sigma = \sum_{s \in S} s is even and ∑s∈S1s=Σ/2\sum_{s \in S_1} s = \Sigma / 2. The problem assumes the input is encoded in binary, with the input size measured by nn (the number of elements) and the aggregate of the integers, which can be up to O(nlog⁡max⁡si)O(n \log \max s_i). A "yes" instance can be verified in time by checking that the provided subset sums to exactly Σ/2\Sigma / 2, confirming the problem's membership in NP via non-deterministic guessing of the subset followed by deterministic summation. An associated optimization variant seeks to partition SS into two subsets S1S_1 and S2S_2 minimizing ∣∑s∈S1s−∑s∈S2s∣|\sum_{s \in S_1} s - \sum_{s \in S_2} s|, which generalizes the decision version by allowing unequal sums and focusing on the minimal achievable difference. This formulation highlights the problem's roots in subset sum, where the target is fixed at half the total, distinguishing it from unrestricted partitioning tasks in that lack sum constraints. The pseudo-polynomial nature arises because solvability depends on the numeric magnitudes (e.g., via dynamic programming over possible subset sums up to Σ/2\Sigma / 2), which grow exponentially with bit length but polynomially with the unary-encoded values. The partition problem is equivalent to determining whether there exists a subset of the given multiset whose elements sum to exactly half the total sum of all elements, provided the total sum is even; this directly reduces to the subset-sum problem with the target value set to half the total. In its optimization variant, the problem seeks to minimize the absolute difference between the sums of the two subsets, formulated as finding a subset S1S_1 that minimizes ∣2⋅∑x∈S1x−∑x∈Sx∣|2 \cdot \sum_{x \in S_1} x - \sum_{x \in S} x|, where SS is the full multiset; the decision version checks if this minimum difference is zero. The problem is typically defined over multisets of integers, allowing duplicate values, though the NP-completeness holds equivalently for sets without duplicates, as the presence of multiples does not alter the fundamental . Standard formulations assume positive integers, ensuring non-trivial partitioning; allowing negative integers or zeros alters the problem dynamics, potentially rendering it polynomial-time solvable in some cases (e.g., negatives enable arbitrary sum adjustments via balancing), but the case restricts to positives to maintain computational intractability.

Illustrative Examples

Basic Examples

A basic feasible instance of the partition problem is the S={1,1,2,3,1,2}S = \{1, 1, 2, 3, 1, 2\}, with total sum 10; one valid partition is S1={1,1,1,2}S_1 = \{1, 1, 1, 2\} and S2={3,2}S_2 = \{3, 2\}, each summing to 5. Another simple case is S={1,2,3}S = \{1, 2, 3\}, with total sum 6 (even) and partitions {1,2}\{1, 2\} and {3}\{3\}, both summing to 3. A necessary condition for feasibility is that the total sum must be even, as equal sums require an integer half-sum; if odd, no partition exists. For instance, S={1,2,3,5}S = \{1, 2, 3, 5\} has sum 11 (odd), rendering it immediately infeasible without . For small sets like these (n≤4n \leq 4), exhaustive of 2n2^n subsets verifies solutions manually, as the subset sum possibilities are few and computable by inspection; e.g., in S={1,5,11,5}S = \{1, 5, 11, 5\} (sum 22), checking subsets confirms {1,5,5}\{1, 5, 5\} and {11}\{11\} both sum to 11. Such cases illustrate that while trivial instances yield quick resolutions, the problem's challenge emerges with larger nn.

Non-Trivial Cases

A necessary condition for a feasible partition is that the total sum of the elements is even, as the sums of the two subsets must each equal half the total. If the sum is odd, partitioning is immediately impossible. For instance, with S = {1, 2, 4}, the sum is 7, which is odd, precluding any equal-sum subsets. In contrast, consider S = {1, 5, 5, 11}, where the total sum is 22 (even), and half is 11. A valid partition is {11} and {1, 5, 5}, but identifying it requires systematic rather than immediate inspection, as no single element or obvious pair matches the target without trial. Brute-force resolution involves checking up to 2^n for a sum of total/2, yielding in effort; for n=40, this exceeds 1 trillion subsets, rendering exhaustive search impractical without optimization. Partition symmetries—where a and its complement represent the same division—halve the effective search to roughly 2^{n-1} unique cases, yet the scaling remains prohibitive for large n. Real-world instances often feature structured inputs, such as numbers of comparable magnitudes (e.g., from resource allocation or load balancing), which enable heuristic pruning but still demand careful analysis beyond naive enumeration to avoid overlooking viable partitions.

Historical Context

Origins and Early Recognition

The partition problem, which seeks to determine whether a multiset of positive integers can be divided into two subsets of equal sum, traces its conceptual origins to early combinatorial optimization and operations research, predating the NP-completeness era. Emerging without a singular inventor, it arose organically from practical challenges in partitioning resources, such as load balancing in manufacturing and equitable division in economic planning, where manual computations for small datasets were routine in the mid-20th century. For instance, operations researchers in the 1950s and 1960s encountered analogous tasks when allocating indivisible items—like production batches or assets—to minimize imbalances, often solving them exhaustively for sets of fewer than 20 elements due to exponential growth in possibilities. Closely related to the , the partition formulation gained traction through dynamic programming advancements. In 1957, Richard Bellman developed a for subset sum, enabling solutions in O(nt) time where n is the number of elements and t the target sum; applying this to partition by setting t to half the total sum provided an early computational approach, though limited to moderate-sized inputs by memory constraints of the era. This method underscored the problem's solvability for practical scales but highlighted its intractability for larger instances, as evidenced by empirical tests in optimization literature. By the 1960s, the problem surfaced explicitly in multiprocessor scheduling contexts within . Ronald Graham's analyses of scheduling on identical processors, starting with his 1966 work on anomaly bounds and culminating in 1969 bounds for minimization, revealed the two-processor case as equivalent to partition: assigning jobs to minimize completion time reduces to balancing subset sums. These connections extended to knapsack and early bin-packing heuristics, where partitioning decisions optimized storage or transport efficiency, reflecting the problem's role in real-world without formal classifications.

Establishment as NP-Complete

The partition problem was formally recognized as NP-complete by Richard M. Karp in his 1972 paper "Reducibility Among Combinatorial Problems," which demonstrated its membership in a set of 21 combinatorial decision problems proven via chains of polynomial-time many-one reductions originating from the problem or established intermediates like subset sum. Karp's reductions positioned partition equivalently hard to these foundational problems under the emerging theory of , highlighting its intractability for general instances while underscoring the practical implications for optimization tasks in . This establishment occurred in the proceedings of a on the Complexity of Computer Computations, held March 20–22, 1972, at , building directly on Stephen Cook's 1971 definition of through . By including partition among the 21 problems—spanning , logic, and number partitioning—Karp's work illustrated the breadth of across disparate domains, facilitating subsequent analyses of problem hardness and approximation viability. Distinct from strongly NP-complete variants like 3-partition, the standard partition problem exhibits weak , attributable to its solvability via algorithms sensitive to the numerical magnitudes in the input rather than exponential in bit length alone. This characteristic, implicit in Karp's reductions which preserve boundedness but not unary encoding hardness, distinguishes partition's theoretical profile and informs its treatment in classifications.

Computational Complexity

NP-Completeness Proof

The belongs to NP, as a proposed certificate consists of a of the input elements, which can be verified in polynomial time by computing the subset sum and checking whether it equals half the total sum of all elements (after confirming the total sum is even). To establish , there exists a polynomial-time from the subset-sum problem—which is —to the partition problem. Given a subset-sum instance (X,C)(X, C) where X={x1,…,xn}X = \{x_1, \dots, x_n\} is a set of positive integers and CC is the target sum with 0≤C≤S0 \leq C \leq S and S=∑xiS = \sum x_i, construct the partition instance Y=X∪{C+1,S−C+1}Y = X \cup \{C + 1, S - C + 1\}. The total sum of YY is 2S+22S + 2, so half is S+1S + 1. This reduction preserves yes-instances and no-instances. If there exists a of XX summing to CC, then adjoining S−C+1S - C + 1 yields a of YY summing to S+1S + 1, with the complementary (including C+1C + 1) also summing to S+1S + 1. Conversely, if YY admits a partition into two s each summing to S+1S + 1, then—given positive integers and the inability to place both added elements in one (summing to S+2>S+1S + 2 > S + 1) or neither (maximum sum from XX is S<S+1S < S + 1)—one must contain S−C+1S - C + 1 paired with a of XX summing exactly to CC. The construction runs in polynomial time, as it requires a single pass to compute SS and append two elements. This reduction demonstrates that any polynomial-time algorithm for partition would imply one for subset sum, confirming the NP-hardness of partition for positive integer instances. The result aligns with Richard Karp's 1972 classification of partition among 21 core NP-complete problems via systematic reductions.

Pseudo-Polynomial Time Solvability

The partition problem can be solved exactly using dynamic programming in pseudo-polynomial time. Let the input set consist of nn positive integers with total sum SS, and assume SS is even for a potential partition (otherwise, no solution exists). Define target T=S/2T = S/2. A boolean array dp[0…T]dp[0 \dots T] tracks achievable subset sums, initialized with dp{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}} = true and others false. For each integer xx in the set, iterate backward from s=Ts = T down to xx, setting dp=dp∨dp[s−x]dp = dp \lor dp[s - x]. The solution exists if dp[T]dp[T] is true at the end. This approach yields time complexity O(nT)=O(nS)O(nT) = O(nS), which is polynomial in the unary representation of the input numbers but exponential in their binary bit lengths, hence pseudo-polynomial. Space usage is O(T)O(T), optimizable further by tracking only the previous row in a 2D formulation or using bitsets for denser storage in practice. The algorithm's efficiency stems from exploiting the numeric magnitudes directly, contrasting with exponential dependence on nn in brute-force enumeration. The pseudo-polynomial nature highlights that computational difficulty in partition instances primarily arises from large integer values rather than solely from the cardinality nn. For bounded number sizes, the problem reduces to polynomial time, enabling solvability for moderate nn (e.g., up to hundreds) and SS (e.g., up to millions) within seconds on standard hardware, as the O(nS)O(nS) operations remain tractable before memory or time limits bind.

Weak NP-Hardness Characteristics

The partition problem is classified as weakly NP-complete, indicating that while it is NP-hard under binary encoding of input numbers, it possesses a pseudo-polynomial time algorithm that resolves instances exactly when the numeric values do not grow exponentially with the input length. This dynamic programming approach operates in O(nS) time, where n is the number of elements and S is half the total sum, rendering it polynomial-time solvable if the numbers are bounded by a polynomial function of n. In contrast, strongly NP-hard problems, such as 3-partition, maintain their hardness even when numbers are encoded in unary or bounded polynomially in magnitude, precluding pseudo-polynomial algorithms and emphasizing inherent combinatorial intractability independent of number sizes. The distinction, formalized by Garey and Johnson, underscores that weak NP-hardness arises from the bit-length sensitivity of large numbers rather than structural complexity alone. This weak characterization tempers assertions of the partition problem's intractability, as practical instances often feature sums amenable to exact computation via dynamic programming, particularly when n is moderate and numbers lack extreme exponential scaling. Garey and Johnson explicitly categorize partition under weakly NP-complete problems like subset sum, distinguishing them from strongly NP-complete variants that resist such efficient exploitation.

Solution Approaches

Exact Algorithms

The dynamic programming algorithm provides a pseudo-polynomial time exact solution by solving the equivalent to target S/2S/2, where SS is the total sum of the nn integers, provided SS is even. A boolean array dp[0…S/2]dp[0 \dots S/2] is initialized with dp{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}} = true. For each integer aia_i, the array is updated backwards: for jj from S/2S/2 down to aia_i, set dp=dp∨dp[j−ai]dp = dp \lor dp[j - a_i]. A partition exists if dp[S/2]=truedp[S/2] = true. The time complexity is O(nS)O(nS), with space O(S)O(S), making it efficient when sums are small but impractical for large SS. For instances with small nn but large numbers, where dynamic programming is infeasible due to sum size, meet-in-the-middle algorithms offer exponential-time exact solutions. The set is split into two subsets of roughly n/2n/2 elements each. All 2n/22^{n/2} subset sums are computed for both halves, one list is sorted, and for each sum uu from the second half, binary search checks for S/2−uS/2 - u in the first. This achieves O(2n/2nlog⁡n)O(2^{n/2} n \log n) time. The Schroeppel-Shamir algorithm refines this to O(2n/2)O(2^{n/2}) time using sorted sum pairs and modular arithmetic, with space reduced to O(2n/4)O(2^{n/4}), enabling solution of instances up to n≈40n \approx 40. Branch-and-bound methods systematically explore the assignment of numbers to subsets, pruning branches where the current sum difference exceeds the maximum possible adjustment from remaining numbers. Korf's complete Karmarkar-Karp (CKK) algorithm, an anytime branch-and-bound variant, sorts numbers decreasingly, applies differencing to maintain a priority queue of partial differences, and backtracks to guarantee optimality. It solves random instances with up to 100 numbers in seconds on 1990s hardware, outperforming naive enumeration through tight bounds and heuristics for variable ordering. No major theoretical improvements beyond these techniques have emerged since the 1980s, though implementations continue to optimize pruning and parallelism for practical sizes.

Approximation Algorithms

The greedy algorithm, also known as the longest processing time (LPT) rule adapted for two subsets, sorts the input numbers in descending order and iteratively assigns each number to the subset with the currently smaller sum. This method guarantees that the larger subset sum is at most 76\frac{7}{6} times the optimal larger sum in the worst case. The approximation ratio arises from analysis showing that the algorithm's makespan exceeds the optimum by at most one-third of the largest item relative to the optimum, tightened for two subsets. The Karmarkar-Karp (KK) differencing heuristic provides another approach with strong empirical performance. It begins by sorting numbers descending, then repeatedly selects the two largest values x≥yx \geq y, removes them, and inserts x+yx + y and x−yx - y back into the list, resorting after each step until two values remain; their difference estimates the minimum imbalance, and backtracking yields a partition. While lacking a proven constant-factor worst-case ratio, KK often produces solutions with differences exponentially smaller than the greedy on random instances and outperforms it on structured cases. Worst-case analysis of the greedy confirms its 76\frac{7}{6}-approximation bound holds tightly for instances like multiples of three equal numbers plus smaller adjustments, where the algorithm achieves nearly 76\frac{7}{6} OPT. More advanced schemes exist via dynamic programming scaling, yielding (1 + \epsilon)-approximations in time polynomial in nn and 1/ϵ1/\epsilon, exploiting the problem's weak NP-hardness.

Heuristic and Metaheuristic Methods

The Karmarkar-Karp (KK) differencing heuristic, introduced in 1982, iteratively pairs the two largest remaining numbers in the multiset, replaces them with their absolute difference, and repeats until a single value remains, which approximates the minimum partition difference. This process exploits the intuition that assigning large numbers to opposite subsets minimizes imbalance, with reconstruction of the actual partition achieved by tracing the differencing history backward. The complete variant, CKK, extends this by branching on unresolved choices during differencing to explore optimality branches, but as a heuristic, the basic iterative differencing yields polynomial-time solutions suitable for large instances without exhaustive search. Metaheuristics such as genetic algorithms (GAs) and simulated annealing (SA) address the limitations of greedy heuristics like KK by incorporating stochastic exploration and local improvements. GAs represent partitions as binary strings or vectors assigning numbers to subsets, evolving populations through crossover, mutation, and selection to minimize sum differences, often outperforming KK on structured instances by maintaining diversity in solution space. SA, inspired by statistical mechanics, starts from an initial partition and perturbs it (e.g., by swapping elements between subsets), accepting worsening moves with probability decreasing over "temperature" schedule to escape local optima. These methods leverage locality in the solution landscape, where neighboring partitions differ by small swaps, enabling effective search for near-optimal balances in high-dimensional spaces. Empirical evaluations demonstrate that such heuristics scale to massive instances; for example, sorted KK variants achieve differences exponentially small in nn for random inputs with nn up to thousands, completing in O(nlog⁡n)O(n \log n) time dominated by sorting and priority queue operations. GAs and SA, while slower per iteration, solve n≈103n \approx 10^3 to 10410^4 cases near-optimally within seconds on standard hardware, with hybrids combining KK initialization and local search yielding further gains on non-random data. Post-2020 refinements, including diploid GAs with enhanced encoding for multidimensional variants, incorporate adaptive operators to handle correlated numbers, improving convergence on large-scale problems by modeling allele interactions akin to genetic dominance. These approaches prioritize practical efficacy over guarantees, enabling deployment in resource-constrained settings like scheduling where exact solutions are infeasible.

Difficulty Analysis

Hard Instances

Instances of the partition problem empirically resistant to standard solvers, including exact branch-and-bound and heuristics like Karmarkar-Karp, occur in random integer sets where each number has bit length bb approximately equal to the instance size nn. In this regime, the average number magnitude is roughly 2n−12^{n-1}, yielding a total sum on the order of n⋅2n−1n \cdot 2^{n-1}, which maximizes the combinatorial frustration in subset selection. A sharp phase transition governs this difficulty, parameterized by κ=b/n\kappa = b / n, with the critical point at κc≈1\kappa_c \approx 1 (more precisely, κc=1−log⁡2n/(2n)+O(1/n)\kappa_c = 1 - \log_2 n / (2n) + O(1/n)). For κ<κc\kappa < \kappa_c, instances typically admit many perfect partitions, rendering them easy; for κ>κc\kappa > \kappa_c, no perfect partitions exist, but near κc\kappa_c, the probability of exact equality plummets while near-matches proliferate, peaking solver runtimes as the effective search space expands exponentially before collapsing into sparser sums. The underlying cause is the maximization of subset-sum entropy near the transition: the distribution of possible subset sums forms a narrow Gaussian around half the total with width comparable to the target precision, densely filling the vicinity but probabilistically evading the exact midpoint due to finite granularity and independence of number contributions. This creates a landscape of balanced yet non-partitionable configurations, where algorithms like complete differencing equate to near-blind enumeration, as verified in simulations averaging over thousands of instances.

Phase Transitions and Empirical Behavior

In random instances of the partition problem, where the input consists of nn integers drawn uniformly from [1,M][1, M], a threshold phenomenon emerges in the probability of achieving a perfect partition (subsets with equal sum). Simulations indicate that this probability transitions sharply from near 1 to near 0 as MM exceeds approximately 2n/n2^n / n, reflecting the point where the number of possible subset sums (2n2^n) becomes comparable to the total sum scale (nMnM). For M≪2n/nM \ll 2^n / n, the subset sums densely cover the range up to the total sum, enabling near-perfect partitions via fine-grained combinations; beyond the threshold, sums become sparse, making exact equality unlikely without exhaustive search. Empirical studies parameterize difficulty via κ=log⁡2M/n\kappa = \log_2 M / n, revealing maximal near κ≈1\kappa \approx 1, where solving times for exact methods peak due to balanced in subset sum distributions. For instance, simulations with nn up to 100 and varying bit lengths show that instances with average number sizes around nn exhibit the longest runtimes for dynamic programming or branch-and-bound, as the aligns with the absence of exploitable structure. At extremes—low κ\kappa (small, numerous additive options) or high κ\kappa (dominated by large numbers amenable to greedy assignment)—instances solve rapidly, with approximation ratios approaching 1 even for heuristics. This behavior underscores that the partition problem's intractability is not uniform; practical applications, such as load balancing with n≤50n \leq 50 and bounded magnitudes (e.g., M<106M < 10^6), typically fall below the transition, yielding solvable cases without full enumeration. Recent empirical analyses confirm that input distributions skewed toward smaller values further mitigate hardness, with bit variance explaining up to 80% of runtime differences in benchmark simulations. Thus, while theoretical worst-case bounds highlight NP-hardness, statistical patterns from random ensembles reveal tractable regimes dominating real-world data.

Variants and Generalizations

Multiway Partition Problems

The k-partition problem generalizes the two-way partition problem by requiring the division of a multiset of n positive integers into k subsets (k ≥ 3 fixed), each with equal sum S/k, where S is the total sum (assumed divisible by k); the decision version asks whether such a partition exists. Unlike the k=2 case, which admits a pseudo-polynomial dynamic programming algorithm, the k-partition problem for fixed k ≥ 3 lacks pseudo-polynomial solvability unless P=NP, due to its strong NP-hardness even when input numbers are polynomially bounded. The 3-partition problem, a canonical instance with k=3, requires partitioning 3m integers into m triples each summing to a target B; it is strongly NP-complete, as established via reductions preserving polynomial bounds on numbers. This strong intractability extends to general fixed k ≥ 3 through analogous reductions, precluding pseudo-polynomial algorithms and necessitating exponential-time exact methods or approximations for practical instances. In scheduling applications, k-partition models load balancing on k identical parallel machines to minimize makespan, where job processing times form the multiset and equal-sum subsets correspond to balanced machine loads; the decision version for makespan at most S/k reduces directly to k-partition, inheriting its strong NP-hardness. Such reductions highlight the problem's utility in proving intractability for multiprocessor scheduling variants with identical machines.

Probabilistic and Stochastic Variants

In probabilistic variants of the partition problem, the input integers are drawn randomly from specified distributions, such as uniform distributions over intervals, to analyze average-case performance metrics like the probability of an exact partition or the expected value of the minimal difference between subset sums. For instances where nn positive integers are chosen independently and uniformly at random from {1,2,…,2cn}\{1, 2, \dots, 2^{cn}\} for constant c>0c > 0, the expected optimum (minimal difference) is at most O(2−n2/log⁡n)O(2^{-n^2 / \log n}), exponentially small in nn. This reflects that random instances are typically "easy" in terms of , as near-perfect partitions exist with high probability, though exact solvability remains improbable for large nn due to the . Stochastic variants extend this by treating inputs as realizations of random variables, often to model uncertainty in sums, and evaluate metrics such as the probability that a partition achieves sums within a probabilistic bound or the expected approximation ratio over distributions. For example, when numbers follow a Gaussian distribution or other continuous analogs discretized for the problem, the solvability probability—defined as the likelihood of finding subsets with difference at most ϵ\epsilon times the total sum—decays based on variance parameters, enabling analysis of robustness to noise in input generation. Recent studies emphasize how the distribution of informational bits (the binary digits contributing to the total sum's magnitude) across the nn integers impacts dynamic programming efficiency: uneven bit allocation, such as concentrating most bits in fewer numbers, reduces the effective state space explored in exact algorithms compared to uniform distribution, altering runtime from exponential in total bits mm to dependencies on both nn and bit concentration. This bit-distribution effect holds for the standard O(n⋅Σ/2)O(n \cdot \Sigma/2) DP, where Σ\Sigma is the total sum, as sparse bit patterns lead to fewer viable partial sums, improving practical solvability without changing worst-case complexity.

Other Extensions

The graph partitioning problem serves as an analog to the number partition problem, involving the division of a graph's vertices into subsets of roughly equal (or total weight) while minimizing the weight of edges crossing between subsets, thereby balancing connectivity costs akin to sum discrepancies. This formulation arises in for load distribution and VLSI design, where it exhibits even for balanced bisections. In geometric contexts, the partition problem extends to sets of points or vectors in , requiring subsets whose vector sums—or higher-order moments such as centroids—balance as closely as possible; this multidimensional variant captures applications in spatial load balancing and , inheriting from the scalar case but with added geometric constraints like spatial coherence. A 2024 variant, the Maximum Zero-Sum Partition (MZSP) problem, seeks a maximum-cardinality collection of disjoint zero-sum subsets from a of non-zero integers, with relevance to for modeling evolutionary distances via balanced cancellations; it is NP-hard in general, solvable via dynamic programming for bounded subset sizes, and extends the core problem by prioritizing exhaustive zero balances over mere bipartition. These generalizations typically retain the weak NP-hardness of the original for polynomially bounded inputs, contrasting with strongly NP-hard multidimensional forms.

Applications

Theoretical and Computational Uses

The partition problem is classified as weakly NP-complete, meaning it admits a algorithm—dynamic programming with O(nS), where S is the total sum—yet remains NP-hard when inputs are encoded in binary. This contrasts with strongly NP-complete problems, such as 3-partition, which resist pseudo-polynomial solvability unless =NP. Established as NP-complete in the seminal compendium by Garey and Johnson through reduction from subset sum, the problem provides a foundational benchmark for verifying proofs and testing solver encodings, including comparisons between dynamic programming implementations and (SAT) formulations. Reductions from the partition problem are routinely applied to establish in domains like scheduling (e.g., minimizing on identical machines) and cryptographic primitives related to subset sum variants, underscoring its utility in complexity transfers without relying on stronger assumptions. Theoretically, its weak hardness challenges assumptions of uniform intractability across NP, as practical solvability emerges for instances with small S, prompting inquiries into whether P≠NP implies graded difficulties rather than absolute barriers, distinct from problems demanding exponential time regardless of numeric scale.

Practical Real-World Implementations

In and multiprocessor scheduling, the partition problem models the assignment of computational tasks with given execution times to two processors such that the total processing load on each is equalized, minimizing the . This equivalence holds because the decision version checks if task durations can be split into subsets with identical sums, directly reducing to the partition problem for identical machines. Exact dynamic programming solutions are feasible for instances with up to approximately 40 tasks and moderate total sum (e.g., under 10^6), as the is O(nS/2) where S is the total sum, allowing optimal load balance in small-scale systems like embedded multiprocessors. For larger-scale scheduling in or centers, heuristic methods such as the Karmarkar-Karp differencing approximate solutions efficiently, often achieving partition differences below 1% of the total sum in empirical tests on random instances. These approximations scale to hundreds of tasks via greedy refinements, enabling practical deployment in where exact optimality is traded for speed, though suboptimal partitions can increase completion times by up to 10-20% in worst-case synthetic benchmarks. In distributed , such as systems, the problem appears in partitioning data volumes across nodes to balance disk usage and I/O load; for binary splits (e.g., replicating datasets), algorithms seek subsets matching half the total size to prevent hotspots. Heuristics integrated into frameworks like Hadoop's block placement use variant partitioning to approximate even distribution during data rebalancing, reducing variance in node loads by factors of 2-5 compared to naive hashing in simulations of terabyte-scale clusters as of 2015. Contemporary applications in 2020s distributed systems include network traffic management, where packet flows or virtual links are partitioned across routers to equalize bandwidth utilization, employing online variants of partition heuristics to adapt to dynamic loads. In data sharding for databases like , initial shard assignment treats block sizes as partition inputs to minimize imbalance, with solvers handling up to thousands of via local search, though exact methods remain limited to offline planning for n under 100 due to in search space. While heuristics enable scalability, their use in safety-critical environments (e.g., scheduling) necessitates verification against exact solvers to mitigate risks of load disparities exceeding 5%, as suboptimal allocations can cascade to system delays.

References

  1. https://www.geeksforgeeks.org/dsa/set-partition-is-np-complete/
  2. https://dl.acm.org/doi/10.1145/3184400
  3. https://faculty.college.emory.edu/sites/boettcher/Publications/papers/epjb65_131.pdf
  4. https://cs.stackexchange.com/questions/126246/formal-defintion-of-set-partition-as-a-language
  5. https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/aeeb7d25b6b22cb4bfa76671d69a0324_MIT6_046JS12_lec18.pdf
  6. https://arxiv.org/pdf/2405.05544
  7. https://mathoverflow.net/questions/306039/is-this-partition-problem-strongly-np-complete
  8. https://stackoverflow.com/questions/36946607/how-does-the-partition-prob-have-pseudo-polynomial-runtime
  9. https://cs.stackexchange.com/questions/124878/the-partition-problem-reducing-to-prove-np-completeness
  10. https://www.geeksforgeeks.org/dsa/partition-problem-dp-18/
  11. https://stackoverflow.com/questions/69921958/partition-a-set-into-two-subsets-so-that-the-difference-of-the-sum-is-minimum-an
  12. https://www.cs.umd.edu/users/gasarch/COURSES/858/S21/SCRIBES/AlexM3part.pdf
  13. https://www.sciencedirect.com/science/article/pii/S0893965905003903
  14. https://www.finalroundai.com/articles/partition-problem
  15. https://heycoach.in/blog/problem-definition-of-partition-problem/
  16. http://web.cecs.pdx.edu/bart/cs510cs/papers/korf-ckk.pdf
  17. https://arxiv.org/pdf/cond-mat/0310317
  18. https://www.sciencedirect.com/science/article/pii/S0304397507000357
  19. https://www.researchgate.net/publication/365640898_A_historical_note_on_the_complexity_of_scheduling_problems
  20. https://chaoxu.prof/files/papers/subset-sum-simple.pdf
  21. https://cr.yp.to/qsubsetsum/qsubsetsum-20130407.pdf
  22. https://arxiv.org/abs/0808.1119
  23. https://www.cs.virginia.edu/~robins/cs3102/slides/Theory_Slides_NP_Completeness.pdf
  24. https://www.cs.purdue.edu/homes/hosking/197/canon/karp.pdf
  25. https://www.researchgate.net/publication/221580898_Reducibility_Among_Combinatorial_Problems
  26. https://www.ida.liu.se/~TDDD20/info/filer/21-nphard.pdf
  27. https://courses.grainger.illinois.edu/cs473/sp2017/notes/15-nphard.pdf
  28. https://web.cs.unlv.edu/larmore/Courses/CSC456/ssPart.pdf
  29. https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-18-dynamic-programming-part-4-rods-subset-sum-pseudopolynomial/
  30. https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/f62798df9d8020e1c92130bd76a26f20_MIT6_006S20_lec18.pdf
  31. https://courses.csail.mit.edu/6.5440/fall23/scribe/lec2.pdf
  32. https://elementsofscheduling.nl/PDF/Ch02.pdf
  33. https://courses.csail.mit.edu/6.5440/fall23/lectures/L02.pdf
  34. https://cdn.aaai.org/ojs/17424/17424-13-20918-1-2-20210518.pdf
  35. https://dl.acm.org/doi/pdf/10.1145/321812.321823
  36. https://dl.acm.org/doi/10.1145/3406325.3451024
  37. https://www.researchgate.net/publication/326640227_Optimal_Multi-Way_Number_Partitioning
  38. https://www.sciencedirect.com/science/article/pii/S0004370298000861
  39. https://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/CSD-83-113.pdf
  40. https://cdn.aaai.org/FLAIRS/2000/FLAIRS00-020.pdf
  41. https://pubsonline.informs.org/doi/10.1287/opre.39.3.378
  42. https://scholar.harvard.edu/files/peter_chang_portfolio/files/number-partition-heuristics.pdf
  43. https://dl.acm.org/doi/abs/10.1145/3583133.3590672
  44. https://arxiv.org/pdf/cond-mat/9807077
  45. https://link.aps.org/doi/10.1103/PhysRevLett.81.4281
  46. https://arxiv.org/abs/cond-mat/9807077
  47. https://www.scitepress.org/Papers/2023/121436/121436.pdf
  48. https://cstheory.stackexchange.com/questions/5492/np-hardness-of-a-special-case-of-number-partitioning
  49. https://dl.acm.org/doi/pdf/10.1145/322077.322090
  50. https://cs.stackexchange.com/questions/168197/harder-version-of-the-k-partition-problem
  51. https://ojs.aaai.org/index.php/ICAPS/article/download/13544/13393/17062
  52. https://www.researchgate.net/post/When_should_we_use_2_partition_and_3_partition_problems_for_proving_the_complexity_of_scheduling_problems
  53. https://ics.uci.edu/~lueker/papers/exppart.pdf
  54. https://drops.dagstuhl.de/storage/00lipics/lipics-vol274-esa2023/LIPIcs.ESA.2023.37/LIPIcs.ESA.2023.37.pdf
  55. https://www.researchgate.net/publication/375818765_The_Partition_Problem_and_How_The_Distribution_of_Input_Bits_Affects_the_Solving_Process
  56. https://www.sciencedirect.com/topics/computer-science/graph-partition-problem
  57. https://arxiv.org/abs/2406.08329
  58. https://www.sciencedirect.com/science/article/pii/S0307904X13002692
  59. https://www.sciencedirect.com/science/article/pii/S0304397524004286
  60. https://dl.acm.org/doi/10.1016/j.tcs.2024.114811
  61. https://people.orie.cornell.edu/dpw/orie6300/Lectures/lec25.pdf
  62. https://perso.limos.fr/~palafour/PAPERS/PDF/Garey-Johnson79.pdf
  63. https://cs.stackexchange.com/questions/84136/weakly-np-complete-problems-and-strongly-np-complete-problems
  64. https://courses.grainger.illinois.edu/cs598csc/sp2009/lectures/lecture_5.pdf
  65. https://www.sciencedirect.com/science/article/abs/pii/S0167637798000054
  66. https://www.researchgate.net/publication/259399650_Algorithms_Analysis_for_the_Number_Partition_Problem
  67. https://heycoach.in/blog/applications-of-partition-problem-in-data-distribution/
Add your contribution
Related Hubs
Contribute something
User Avatar
No comments yet.