3-partition problem: Difference between revisions

Revision as of 12:59, 6 April 2016

Revision as of 13:47, 22 July 2016

Line 2:

The 3-partition problem is similar to the [[partition problem]], which in turn is related to the [[subset sum problem]]. In the partition problem, the goal is to partition ''S'' into two subsets with equal sum. In 3-partition the goal is to partition ''S'' into ''m'' subsets (or ''n''/3 subsets), not just two subsets, with equal sum.

==Example==

The set { 20, 23, 25, 35, 37, 40 } can be partitioned into the three sets { 20, 40 }, { 25, 35 } and { 23, 37 }, each of which sum to 60.

==Strong NP-completeness==