
Recent Posts
 Annihilation July 12, 2019
 Alternating Maximum Weighted Matching June 28, 2019
 Alternating Hitting Set June 6, 2019
 Sift May 23, 2019
 Avoidance Truth Assignment May 10, 2019
Recent Comments
 Sean T. McCulloch on How to get the archive password
 Yiyang Jia on How to get the archive password
 Sean T. McCulloch on 3Satisfiability
 Surekha on 3Satisfiability
 Gabriel Ferrer on Protected: Quantified Boolean Formulas
Archives
 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
 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: 3Partition
Protected: JobShop Scheduling
Enter your password to view comments.
Posted in Appendix: Sequencing and Scheduling
Tagged 3Partition, Difficulty 2, Difficulty 5, FlowShop Scheduling, JobShop Scheduling, SS18
Protected: FlowShop Scheduling
Enter your password to view comments.
Posted in Appendix: Sequencing and Scheduling
Tagged 3Partition, Difficulty 5, FlowShop Scheduling, OpenShop scheduling, SS15
Protected: Sequencing to Minimize Weighted Tardiness
Enter your password to view comments.
Posted in Appendix: Sequencing and Scheduling
Tagged 3Partition, Scheduling to Minimize Weighted Tardiness, SS5
Protected: Dynamic Storage Allocation
Enter your password to view comments.
Posted in Appendix: Storage and Retrieval
Tagged 3Partition, Difficulty 7, Dynamic Storage Allocation, No G&J reference, Partition Into Cliques, SR2
Protected: Bin Packing Take 2
Enter your password to view comments.
Posted in Appendix: Storage and Retrieval
Tagged 3Partition, Bin Packing, Difficulty 3, No G&J reference, SR1, uncited reduction
Protected: Numerical 3Dimensional Matching
Enter your password to view comments.
Posted in Appendix Sets and Partitions
Tagged 3Partition, 3DM, 4Partition, Difficulty 6, Difficulty 8, Numerical 3Dimensional Matching, SP15, SP16
Protected: Intersection Graph For Segments On A Grid
Enter your password to view comments.
Posted in Appendix Network Design
Tagged 3Partition, Bin Packing, Difficulty 7, Intersection Graph For Segments on a Grid, ND46
Weighted Diameter
It took over a year (the first problem strictly from the Appendix was Domatic Number, last August), but we’re finally at the end of the Graph Theory section! And the last problem is one that’s actually good for students to solve.
The problem: Weighted Diameter. This is problem GT65 in the appendix
The description: Given a graph G=(V,E) a collection C of E not necessarily distinct, nonnegative integers, and a positive integer K. Can we find a onetoone function f mapping each edge in E to an element of C such that if f(e) is the length of edge e, then G has a diameter of K or less.
In other words, given a set of edge weights C, can we give each edge in E a (distinct) weight from C such that the resulting weighted graph has a path between any two vertices of length ≤ K?
Example: Suppose I have a graph:
And C= {1,2,2,2,3,5}. I think the best was you can label this is:
The Diameter here is 7 (The length of the path from AD).
The reduction: G&J say to use 3Partition, so we’ll go with that. We’re given a set A, with 3m elements, a bound B, and want to split the elements of B into sets of size 3 so that each set adds up to m. We know several things about A, but the important thing for our purposes is that all of the elements in A add up to m*B.
We’ll also assume that A is at least 9. If it’s smaller than that, we can just bruteforce the answer.
What we’re going to do is build a graph that is a tree with 3m+1 vertices. We have a root, and the root has m chains of length 3 extending from it. This gives us exactly 3*m edges.
We set K = 2*B, and set C = A
If there exists a 3parition of A, then each of the sets of 3 elements can map onto a different chain in the graph. This makes the longest path in the graph be between any 2 leaves. Since the length from a leaf to a root is exactly B, the diameter of the graph is 2B.
If there exists a weighted diameter of the graph of cost 2*B, then we need to show the the cost of each chain is exactly B. Suppose it wasn’t, and the cost from the root to some leaf v is > B, let’s say B+x. Then , since there are least 3 chains (since A >= 9) and since the sum of all of the weights is m*B exactly), there must exist some leaf w, with the cost of the chain from the root to w > Bx. The cost of the path from v to w is now > 2B, a contradiction.
If the cost from the root to some leaf is < B, then there must be some other leaf u with the cost from the root to u > B (since the cost of all of the edges add up to m*B) , and we can do the above on u.
Since each chain costs exactly B, we can use the edge weights of each chain as the sets of 3 elements that make our 3Partition.
Difficulty: 4. G&J does say in the comments that this problem is NPComplete even for trees, so that may have been a hint. The proof is a little tricky (getting from “diameter ≤ K” to “set adding up to exactly K” requires some work, and there may be a more elegant way than what I did). But I think this would make a good homework problem.
Posted in AppendixGraph Theory
Tagged 3Partition, Difficulty 4, GT65, Weighted Diameter
Protected: Directed Bandwidth
Enter your password to view comments.
Posted in AppendixGraph Theory, Uncategorized
Tagged 3Partition, Bandwidth, Difficulty 10, Directed Bandwidth
Protected: 3Partition
Enter your password to view comments.
Posted in Appendix Sets and Partitions
Tagged 3Partition, 4Partition, Difficulty 8, SP15