3-partition problem: Difference between revisions

Revision as of 11:29, 14 July 2024

Revision as of 09:47, 7 December 2024

Line 31:

The '''ABC-partition problem''' (also called '''[[Numerical 3-dimensional matching|numerical 3-d matching]])''' is a variant in which, instead of a set ''S'' with 3{{hsp|''m''}} integers, there are three sets ''A'', ''B'', ''C'' with ''m'' integers in each. The sum of numbers in all sets is {{tmath|m T}}. 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''.<ref>{{Cite web|last=Demaine|first=Erik|date=2015|title=MIT OpenCourseWare - Hardness made Easy 2 - 3-Partition I|url=https://www.youtube.com/watch?v=ZaSMm2xvatw |archive-url=https://ghostarchive.org/varchive/youtube/20211214/ZaSMm2xvatw |archive-date=2021-12-14 |url-status=live|website=Youtube}}{{cbignore}}</ref>

The '''4-partition problem''' is a variant in which ''S'' contains ''n'' = 4{{hsp|''m''}} integers, the sum of all integers is {{tmath|m T}}, 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-parititonpartition''' is a variant of 4-partition in which each there are 4 input sets and each quadruplet should contain one element from each set.

== Proofs ==