
Recent Posts
 Sift May 23, 2019
 Avoidance Truth Assignment May 10, 2019
 PrePartitioned Truth Assignment April 26, 2019
 Variable Partition Truth Assignment April 12, 2019
 Generalized Kayles March 29, 2019
Recent Comments
 Sean T. McCulloch on 3Satisfiability
 Surekha on 3Satisfiability
 Gabriel Ferrer on Quantified Boolean Formulas
 Sean T. McCulloch on Quantified Boolean Formulas
 Gabriel Ferrer on Quantified Boolean Formulas
Archives
 May 2019
 April 2019
 March 2019
 February 2019
 January 2019
 December 2018
 November 2018
 October 2018
 September 2018
 August 2018
 July 2018
 June 2018
 May 2018
 April 2018
 March 2018
 February 2018
 January 2018
 December 2017
 November 2017
 October 2017
 September 2017
 August 2017
 July 2017
 June 2017
 May 2017
 April 2017
 March 2017
 February 2017
 January 2017
 December 2016
 November 2016
 October 2016
 September 2016
 August 2016
 July 2016
 June 2016
 May 2016
 April 2016
 March 2016
 February 2016
 January 2016
 December 2015
 November 2015
 October 2015
 September 2015
 August 2015
 July 2015
 June 2015
 May 2015
 April 2015
 March 2015
 February 2015
 January 2015
 December 2014
 November 2014
 October 2014
 September 2014
 August 2014
 July 2014
 June 2014
Categories
 Algebra and Number Theory
 Appendix Algebra and Number Theory
 Appendix Automata and Language Theory
 Appendix Games and Puzzles
 Appendix Mathematical Programming
 Appendix Network Design
 Appendix Program Optimization
 Appendix Sets and Partitions
 AppendixGraph Theory
 AppendixLogic
 Appendix: Sequencing and Scheduling
 Appendix: Storage and Retrieval
 Chapter 3 Exercises
 Core Problems
 Overview
 Problems not in appendix
 Uncategorized
Meta
Tag Archives: Part
Protected: Bin Packing
Enter your password to view comments.
Posted in Appendix: Storage and Retrieval
Tagged Bin Packing, Difficulty 2, Part, SR1, uncited reduction
Protected: Integral Flow With Multipliers
Enter your password to view comments.
Posted in Appendix Network Design
Tagged Difficulty 4, Integral Flow with Multipluers, ND33, Part, SOS
Protected: Subset Sum
Enter your password to view comments.
Posted in Appendix Sets and Partitions
Tagged Difficulty 2, Part, SOS, SP13
Protected: Shortest WeightConstrained Path
Enter your password to view comments.
Posted in Appendix Network Design
Tagged Difficulty 5, Part, Shortest WeightConstrained Path, uncited reduction
Protected: Kth Largest Subset and Turing Reductions
Enter your password to view comments.
Posted in Appendix Sets and Partitions
Tagged Difficulty 5, Kth Largest Subset, Part, SP20, Turing Reduction
Protected: Minimum Sum of Squares
Enter your password to view comments.
Posted in Appendix Sets and Partitions, Chapter 3 Exercises
Tagged Difficulty 3, MSS, No G&J reference, Part, reductions, SP19, uncited reduction
Partition
First, an administrative note. I wanted to call this site “Annotated NPComplete Problems”, because the idea is that I’m going through the Garey&Johnson book and adding notes to each problem talking about how to do the reduction and how applicable it is for student assignments. But that name is sort of taken already, and I don’t want to step on any toes or cause any confusion. So I figured that I’d change the title now, before anyone finds out about the site.
And as I’ve been writing, these notes feel more like “discussions” than “short annotations” anyway, so I think this is a better title.
This is the last of the “core six” problems in the G&J book, as defined in Chapter 3. There are several other problems presented in that chapter, with proofs, but since the point of this exercise is to get to the problems without proofs, I’m going to skip over them, and come back to them only if I need to (because they’re the basis for a future reduction, for example).
The problem: Partition (PART)
The definition: Given a set of integers A, can I fid a subset A’⊆A such that the sum of all of the elements in A’ is exactly half the sum of all of the elements in A?
(Alternately, given a set of integers A, can I split all of the elements of A into two subsets B and C, such that the sum of all of the elements in B is equal to the sum of all of the elements in C?)
(Alternately (this is the G&J definition), given any set A, where each element a∈A has a size s(z) that is a positive integer, can we find a subset A’ of A where the sum of the sizes of everything in A’ is exactly equal to the sum of the sizes of everything in AA’?)
Example: Suppose A was the set {1,2,3,4,6}. Then A’ could be {1,3,4}, forming a partition (A’ and AA’ both sum to 8). If instead, A was the set {1,2,3,4,5}, then no possible partition exists. This may seem like a silly case (any set A where the sum of the elements is odd has no partition), but even if the sum of the elements of A is even, it’s possible that no partition exists for example if A is {2,4,100}.
Note: Partition is one of my favorite NPComplete problems, because the description is so easy, and it seems so simple. It’s probably my goto example if I want to explain this stuff to nontechnical people in under a minute pretend that the elements of A are weights, and the value of each element is the weight in ounces. The partition problem asks “given this group of weights, and a scale, can you make the scale balance using all of the given weights?”. It’s pretty surprising to most people that the only known way to answer that question basically boils down to “try all possible combinations of arranging things on the scale”
The reduction: From 3DM. G&J provide the reduction on pages 6162. The basic idea is to have one element in A for each element in M, and to represent the elements in A as binary numbers that have 1’s in positions corresponding to which element from W, X, and Y we get the triple from. The number is set up so that we have a maximum possible value of the sum of all of these elements in A. They then add two “extra” elements to A so that each side of the partition (elements of M that make a matching, and everything else) will add up to the same value
Difficulty: 7. The idea of using binary numbers to keep track of “positions” in a list is tricky, but comes up in lots of places. If students have seen that idea before, this becomes a hard but doable problem. If students haven’t seen that idea before, I’d make this a 9.