The 3-partition problem is a strongly NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triplets that all have the same sum. More precisely:
The 3-partition problem remains strongly NP-complete under the restriction that every integer in S is strictly between T/4 and T/2.
The 3-partition problem remains NP-complete even when the integers in S are bounded above by a polynomial in n. In other words, the problem remains NP-complete even when representing the numbers in the input instance in unary. i.e., 3-partition is NP-complete in the strong sense or strongly NP-complete. This property, and 3-partition in general, is useful in many reductions where numbers are naturally represented in unary.
The 3-partition problem is similar to the partition problem, in which the goal is to partition S into two subsets with equal sum, and the multiway number partitioning, in which the goal is to partition S into k subsets with equal sum, where k is a fixed parameter. In 3-Partition the goal is to partition S into m = n/3 subsets, not just a fixed number of subsets, with equal sum. Partition is "easier" than 3-Partition: while 3-Partition is strongly NP-hard, Partition is only weakly NP-hard - it is hard only when the numbers are encoded in non-unary system, and have value exponential in n. When the values are polynomial in n, Partition can be solved in polynomial time using the pseudopolynomial time number partitioning algorithm.
In the unrestricted-input variant, the inputs can be arbitrary integers; in the restricted-input variant, the inputs must be in (T/4, T/2). The restricted version is as hard as the unrestricted version: given an instance Su of the unrestricted variant, construct a new instance of the restricted version Sr ≔ {s + 2 T | s ∈Su}. Every solution of Su corresponds to a solution of Sr but with a sum of 7 T instead of T, and every element of Sr is in [2 T , 3 T ] which is contained in ( T /4, 7 T /2).
In the distinct-input variant, the inputs must be in (T/4, T/2), and in addition, they must all be distinct integers. It, too, is as hard as the unrestricted version. [1]
In the unrestricted-output variant, the m output subsets can be of arbitrary size - not necessarily 3 (but they still need to have the same sum T). The restricted-output variant can be reduced to the unrestricted-variant: given an instance Sr of the restricted variant, with 3m items summing up to mT, construct a new instance of the unrestricted variant Su ≔ {s + 2T | s ∈Sr}, with 3m items summing up to 7mT, and with target sum 7 T . Every solution of Sr naturally corresponds to a solution of Su. Conversely, in every solution of Su, since the target sum is 7 T and each element is in ( T /4, 7 T /2), there must be exactly 3 elements per set, so it corresponds to a solution of Sr.
The ABC-partition problem (also called numerical 3-d matching) is a variant in which, instead of a set S with 3 m integers, there are three sets A, B, C with m integers in each. The sum of numbers in all sets is . The goal is to construct m triplets, each of which contains one element from A, one from B and one from C, such that the sum of each triplet is T. [2]
The 4-partition problem is a variant in which S contains n = 4 m integers, the sum of all integers is , and the goal is to partition it into m quadruplets, all with a sum of T. It can be assumed that each integer is strictly between T/5 and T/3. Similarly, ABCD-parititon is a variant of 4-partition in which each there are 4 input sets and each quadruplet should contain one element from each set.
Garey and Johnson (1975) originally proved 3-Partition to be NP-complete, by a reduction from 3-dimensional matching. [3] The classic reference by Garey and Johnson (1979) describes an NP-completeness proof, reducing from 3-dimensional matching to 4-partition to 3-partition. [4] Logically, the reduction can be partitioned into several steps.
We are given an instance of E of 3d-matching, containing some m triplets {wi,xj,yk}, where the vertices are w1,...,wq and x1,...,xq and y1,...,yq. We construct an instance of ABCD-partition as follows (where r := 32q):
Given a perfect matching in E, we construct a 4-partition of ABCD as follows:
In both cases, the sum of the 4-set is 40r4 as needed.
Given a partition of ABCD, the sum of each 4-set is 40r4. Therefore, the terms with r, r2 and r3 must cancel out, and the terms with r4 must sum up to 40r4; so the 4-set must contain a triplet and 3 matching "real" elements, or a triplet and 3 matching "dummy" elements. From the triplets with the 3 matching "real" elements, we construct a valid perfect matching in E.
Note that, in the above reduction, the size of each element is polynomial in the input size; hence, this reduction shows that ABCD-partition is strongly NP-hard.
Given an instance of ABCD-partition with m elements per set, threshold T, and sum mT, we construct an instance of 4-partition with 4m elements:
All in all, the sum is 16mT+15m, and the new threshold is 16T+15.
Every ABCD-partition corresponds naturally to a 4-partition. Conversely, in every 4-partition, the sum modulo 16 is 15, and therefore it must contain exactly one item with size modulo 16 = 1, 2, 4, 8; this corresponds to exactly one item from A, B, C, D, from which we can construct an ABCD-partition.
Using a similar reduction, ABC-partition can be reduced to 3-partition.
We are given an instance A of 4-partition: 4m integers, a1,...,a4m, each of which in the range (T/3,T/5), summing up to mT. We construct an instance B of 3-partition as follows:
Given a 4-partition of A, we construct a 3-partition for B as follows:
Conversely, given a 3-partition of B, the sum of each 3-set is a multiple of 4, so it must contain either two regular items and one pairing item, or two pairing items and one filler item:
The NP-hardness of 3-partition was used to prove the NP-hardness rectangle packing, as well as of Tetris [5] [6] and some other puzzles, [7] and some job scheduling problems. [8]
The knapsack problem is the following problem in combinatorial optimization:
In combinatorial mathematics, a Steiner system is a type of block design, specifically a t-design with λ = 1 and t = 2 or (recently) t ≥ 2.
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target-sum , and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP-hard. Moreover, some restricted variants of it are NP-complete too, for example:
In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.
In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory.
Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems. Suppose one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint.
In number theory and computer science, the partition problem, or number partitioning, 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".
In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.
In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices.
In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection problem is to find a common independent set with the maximum possible weight. These problems generalize many problems in combinatorial optimization including finding maximum matchings and maximum weight matchings in bipartite graphs and finding arborescences in directed graphs.
Numerical 3-dimensional matching is an NP-complete decision problem. It is given by three multisets of integers , and , each containing elements, and a bound . The goal is to select a subset of such that every integer in , and occurs exactly once and that for every triple in the subset holds. This problem is labeled as [SP16] in.
In mathematics, the Bell triangle is a triangle of numbers analogous to Pascal's triangle, whose values count partitions of a set in which a given element is the largest singleton. It is named for its close connection to the Bell numbers, which may be found on both sides of the triangle, and which are in turn named after Eric Temple Bell. The Bell triangle has been discovered independently by multiple authors, beginning with Charles Sanders Peirce (1880) and including also Alexander Aitken (1933) and Cohn et al. (1962), and for that reason has also been called Aitken's array or the Peirce triangle.
In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.
Rectangle packing is a packing problem where the objective is to determine whether a given set of small rectangles can be placed inside a given large polygon, such that no two small rectangles overlap. Several variants of this problem have been studied.
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, whose sum is k*T.
The multiple subset sum problem is an optimization problem in computer science and operations research. It is a generalization of the subset sum problem. The input to the problem is a multiset of n integers and a positive integer m representing the number of subsets. The goal is to construct, from the input integers, some m subsets. The problem has several variants:
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.
Matroid-constrained number partitioning is a variant of the multiway number partitioning problem, in which the subsets in the partition should be independent sets of a matroid. The input to this problem is a set S of items, a positive integer m, and some m matroids over the same set S. The goal is to partition S into m subsets, such that each subset i is an independent set in matroid i. Subject to this constraint, some objective function should be minimized, for example, minimizing the largest sum item sizes in a subset. In a more general variant, each of the m matroids has a weight function, which assigns a weight to each element of the ground-set. Various objective functions have been considered. For each of the three operators max,min,sum, one can use this operator on the weights of items in each subset, and on the subsets themselves. All in all, there are 9 possible objective functions, each of which can be maximized or minimized.
