3-partition problem: Difference between revisions

Revision as of 19:38, 10 December 2023

Revision as of 19:08, 1 February 2024

Line 29:

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 ''S_u'' of the restricted variant, construct a new instance of the unrestricted variant {{math|''S_r'' ≔ {s + 2{{hsp{{!}}''T''}} {{!}} s ∈ ''S_u''}}}, with target sum 7{{hsp|''T''}}. Every solution of ''S_u'' naturally corresponds to a solution of ''S_r''. In every solution of ''S_r'', since the target sum is 7{{hsp|''T''}} and each element is in {{nowrap|{{pars|{{hsp|''T''}}/4, 7{{hsp|''T''}}/2}}}}, there must be exactly 3 elements per set, so it corresponds to a solution of ''S_u''.

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'' quadruplesquadruplets, all with a sum of ''T''. It can be assumed that each integer is strictly between ''T''/5 and ''T''/3.

The '''ABC-partition problem''' 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> This problem can be reduced to 3-partition as follows. Construct a set S containing the numbers {{gaps|1000''a''|+|100}} for each {{tmath|a \in A}}; {{gaps|1000''b''|+|10}} for each {{tmath|b \in B}}; and {{gaps|1000''c''|+|1}} for each {{tmath|c \in C}}. Every solution of the ABC-partition instance induces a solution of the 3-partition instance with sum <math>1000(a+b+c)+111 = 1000T+111</math>. Conversely, in every solution of the 3-partition instance, all triplet-sums must have the same hundreds, tens and units digits, which means that they must have exactly 1 in each of these digits. Therefore, each triplet must have exactly one number of the form {{gaps|1000''a''|+|100}}, one {{gaps|1000''b''|+|10}} and one {{gaps|1000''c''|+|1}}. Hence, it induces a solution to the ABC-partition instance.

Line 37:

== Proofs ==

Garey and Johnson (1975) originally proved 3-Partition to be NP-complete, by a reduction from [[3-dimensional matching]].<ref>[[Michael Garey|Garey, Michael R.]] and [[David S. Johnson]] (1979), ''Computers and Intractability; A Guide to the Theory of NP-Completeness''. {{ISBN|0-7167-1045-5}}. Pages 96–105 and 224.</ref> The classic reference by Garey and Johnson (1979) describes an NP-completeness proof, reducing from 3-dimensional matching to 4-partition to 3-partition.<ref>{{cite journal|author=[[Michael Garey|Garey, Michael R.]] and [[David S. Johnson]]|year=1975|title=Complexity results for multiprocessor scheduling under resource constraints|journal=SIAM Journal on Computing|volume=4|issue=4|pages=397–411|doi=10.1137/0204035}}</ref>

=== Reduction from 4-partition to 3-partition ===

We are given an instance ''A'' of 4-partition: 4''m'' integers, a₁,...,a_4m, each of which in the range (T/3,T/5), summing up to ''mT''. We construct an instance ''B'' of 3-partition as follows:

* For each ''a_i'' in A, B contains a "regular" element ''w_i'' = 4*(5T+a_i)+1. All in all there are 4''m'' regular elements, summing up to 81mT + 4m.

* For each pair of elements a_i,a_j in A, B contains two "pairing" elements: u_ij = 4*(6T - a_i - a_j)+2 and u_ij' = 4*(5T + a_i + a_j)+2. All in all there are 4''m*''(4''m''-1) pairing elements, summing up to (88mT+16m)*(4''m''-1).

* Additionally, B contains 8m²-3m "filler" elements, with size 20T, and total sum (8m²-3m)*20T.

* All in all, B contains 24m²-3m = 3(8m²-m) elements, with sum (64T+4)*(8m²-m).

* The threshold for the 3-partition instance is 64T+4; note that the sizes of all elements in B are in (16T+1,32T+2).

Given a 4-partition of ''A'', we construct a 3-partition for B as follows:

* For each 4-set {a₁,a₂,a₃,a₄} with sum T, we construct a 3-set {w₁,w₂,u₁₂} with sum 4*(5T+a₁+5T+a₂+6T-a₁-a₂)+1+1+2=64T+4 and another 3-set {w₃,w₄,u₁₂'} with sum 4*(5T+a₃+5T+a₄+5T+a₁+a₂)+1+1+2=64T+4. These sets contain all 4m regular elements and 2m matching pairs of pairing elements.

* From the remaining elements, we construct 3-sets {u_ij,u_ij',filler} with sum 4*(6T-a_i-a_j+5T+a_i+a_j+5T)+2+2=64T+4.

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:

* If a 3-set contains two pairing items u_ij, u_kl and one filler item, then the sum of the two pairing items must be 44T+4 = 4*(5T+6T)+2+2, so they must have matching sizes (a_i+a_j=a_k+a_l). Therefore, by replacing as needed, we can assume that the two pairing items are in fact u_ij and u_ij'. Therefore, the remaining pairing items also consist of ''n'' matching pairs.

* Therefore, the remaining 3-sets can be partitioned into two groups: ''n'' 3-sets containing the items u_ij, and ''n'' 3-sets containing the items u_ij'. In each matching pair of 3-sets, the sum of the two pairing items u_ij+u_ij' is 44T+4, so the sum of the four regular items is 84T+4. Therefore, from the four regular items, we construct a 4-set in A, with sum T.

== Applications ==