The 3-Partition problem (wiki) is a $\text{NP}$-complete problem which is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. It is well-known that the 3SAT problem has a plenty of variants. Are there some variants of the 3-Partition problem discussed in the literature?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Did you try searching for any? You could immediately consider a variant where each integer occurs exactly or at most $k$ times, for some fixed $k$. $\endgroup$– JuhoCommented Mar 8, 2014 at 13:08
-
$\begingroup$ @Juho I searched and found little. Thanks for your hint. I would prefer to the variants which have been considered in the literature. $\endgroup$– hengxinCommented Mar 8, 2014 at 13:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
One variant of 3-partition is the following distinct 3-partition problem, shown to be NP-complete in [1].
Distinct 3-partition
Input: A set $X = \{a_1,a_2,\ldots,a_{3n}\}$ of positive distinct integers, and a positive integer $B$ where $\Sigma_{i=1}^{3n} a_i = nB$, and $B/4 < a_i < B/2$, where $i \in [3n]$.
Question: Is there a partition of $X$ into $n$ triples such that the elements in each triple sum to $B$?
The problem is also NP-complete when $B$ is bounded above by a polynomial in $n$. For an "application", a reduction from the problem is used in [2] to show a certain graph problem is hard.
