3-partition problem: Difference between revisions

Revision as of 09:04, 2 February 2024

Revision as of 09:22, 2 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_r'' of the restricted variant, with 3''m'' items summing up to ''mT'', construct a new instance of the unrestricted variant {{math|''S_u'' ≔ {s + 2''T'' {{!}} s ∈ ''S_r''}}}, with 3m items summing up to 7mT, and with target sum 7{{hsp|''T''}}. Every solution of ''S_r'' naturally corresponds to a solution of ''S_u''. Conversely, in every solution of ''S_u'', 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_r''.

The '''4ABC-partition problem''' is a variant in which, ''S''instead containsof a set ''nS'' =with 43{{hsp|''m''}} integers, thethere are three sets ''A'', ''B'', ''C'' with ''m'' integers in each. The sum of numbers in all integerssets is {{tmath|m T}},. and theThe goal is to partition it intoconstruct ''m'' quadrupletstriplets, alleach withof awhich contains one element from A, one from B and one from C, such that the sum of each triplet is ''T''.<ref>{{Cite Itweb|last=Demaine|first=Erik|date=2015|title=MIT canOpenCourseWare be- assumedHardness thatmade eachEasy integer2 is- strictly3-Partition betweenI|url=https://www.youtube.com/watch?v=ZaSMm2xvatw ''T''|archive-url=https:/5/ghostarchive.org/varchive/youtube/20211214/ZaSMm2xvatw and|archive-date=2021-12-14 ''T''|url-status=live|website=Youtube}}{{cbignore}}</3.ref>

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.

* The ABC-partition problem is also called '''[[Numerical 3-dimensional matching|numerical 3-d matching]]''', as it can also be reduced to the [[3-dimensional matching]] problem: given an instance of ABC-partition, construct a tripartite hypergraph with sides {{tmath|A, B, C}}, where there is an hyperedge {{tmath|(a, b, c)}} for every three vertices in {{tmath|A, B, C}} such that <math>a+b+c = T</math>. A matching in this hypergraph corresponds to a solution to ABC-partition.

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-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.

== Proofs ==

Line 71 ⟶ 69:

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.

=== Reduction from ABCD-partition to ABC-partition ===

We are given an instance of ''ABCD''-partition with ''m'' elements per set, threshold ''T'', and sum ''mT.'' We construct an instance ABC-partition (which for clarity we will call XYZ-paritition) as follows:

* For each ''a_i'' in A, the set X contains a "regular" element ''x_i'' = 5T+''a_i''.

* For each ''b_j'' in B, the set Y contains a "regular" element ''y_j'' = 5T+''b_j''.

* For each pair of elements c_i in C and d_j in D, the set Z contains two "pairing" elements: z_ij = 6T - c_i - d_j and z_ij' = 5T + c_i + d_j. All in all there are m² pairing elements, summing up to 11T*m².

* 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 an ABCD-partition, we construct an XYZ-partition as follows:

* For each 4-set {a₁,b₂,c₃,d₄} with sum T, we construct a 3-set {x₁,y₂,z₃₄} 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.

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