-
Recent Posts
- Matrix Domination December 1, 2023
- Maximum Likelihood Ranking October 27, 2023
- Randomization Test For Matched Pairs October 13, 2023
- Clustering September 29, 2023
- Shapley-Shubik Voting Power September 15, 2023
Recent Comments
Archives
- December 2023
- October 2023
- September 2023
- August 2023
- March 2023
- January 2023
- December 2022
- November 2022
- October 2022
- September 2022
- August 2022
- June 2022
- May 2022
- December 2021
- November 2021
- October 2021
- September 2021
- August 2021
- July 2021
- May 2021
- April 2021
- March 2021
- February 2021
- January 2021
- December 2020
- November 2020
- October 2020
- September 2020
- August 2020
- March 2020
- February 2020
- January 2020
- December 2019
- November 2019
- October 2019
- September 2019
- August 2019
- July 2019
- June 2019
- 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
- Appendix-Graph Theory
- Appendix-Logic
- Appendix: Miscellaneous
- Appendix: Sequencing and Scheduling
- Appendix: Storage and Retrieval
- Chapter 3 Exercises
- Core Problems
- Overview
- Problems not in appendix
- Uncategorized
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 Weight-Constrained Path
Enter your password to view comments.
Posted in Appendix- Network Design
Tagged Difficulty 5, Part, Shortest Weight-Constrained 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 NP-Complete 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 A-A’?)
Example: Suppose A was the set {1,2,3,4,6}. Then A’ could be {1,3,4}, forming a partition (A’ and A-A’ 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 NP-Complete problems, because the description is so easy, and it seems so simple. It’s probably my go-to example if I want to explain this stuff to non-technical 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 “scales of justice” style 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 61-62. 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.