Tag Archives: 3-Partition

Dynamic Storage Allocation

Since Bin Packing was a redo, here is the first real problem in the Storage and Retrieval section.

The problem: Dynamic Storage Allocation.  This is problem SR2 in the appendix.

The description: Given a set A of items.  Each item a in A has size s(a), arrival time r(a) and departure time d(a) (all positive integers).  We’re also given a storage size D.  Can we allocate the items to D “slots” of storage such that:

  • Each item is stored in consecutive slots.  So an element a has to be contained in s(a) adjacent locations from 1 to D.
  • No two items overlap the same slot during the time they are in storage. In other words, if two items a and a’ are mapped to the same slot in D, the must not have any overlap between their arrival and departure times.

Example: Here’s a simple set of items:

Item Number Arrival Departure Size
1 1 2 4
2 2 3 4
3 1 3 2

If D=6, we can store these items by using slots 1-4 to hold both items 1 and 2 (notice that they don’t overlap in time, and having one item arrive right as the other departs is ok), and slots 5-6 to hold item 3.

Reduction: The reference to Stockmeyer in G&J is to a private communication.  I tried working out my own reduction from 3-Partition, but couldn’t make it work.  My approach was to make the sizes of the elements in the 3-Parttion instance map to times in this problem, since G&J give the hint that you can make all sizes 1 or 2.  But I couldn’t figure out how to make it work.  I sort of expect there to be 3 possible sizes for a 3-partition problem, instead of 2.

Eventually, I found a paper by Lim that uses regular Partition, using the storage allocation problem as a special case of a problem involving berthing ships.   (The ship problem adds extra complications like each ship needing a specified clearance between it and other ships).  He starts with a set A of elements, and defines T to be the sum of all of the element sizes.  He then creates one item in the storage allocation problem for each element in S.  For a given s(a) in A, the new item has size s(a), arrival time 2, departure time 3 (so exist for just one time duration) .  He also adds 9 new items that have the effect of creating only two sequences of storage slots that can hold the items from s, each of size= T/2. We can place the items in these slots if and only if there is a partition of S.

Difficulty: 7.  I don’t think the idea is too hard to understand, but the 9 sets that are created are hard to come up with (even if you can understand what their purpose is, coming up with the sets that actually get that purpose accomplished is pretty hard).

Bin Packing Take 2

[So WordPress’s search function has failed me.  A search for posts on Bin Packing didn’t turn up this post, so I went ahead and wrote a whole second post for this problem.  Since this time my reduction uses 3-Partition instead of Partition (and so is a little less trivial for use as a homework problem), I figured I’d leave it for you as an alternate reduction.

I have been thinking off and on about whether it would be useful when I’m done with this project (years from now) to go back and try to find reductions that can be done easier (or harder) than what I’ve shown here, to give more options that are in the 3-6 difficulty range that I think is best for homework problems.  I’m not sure how feasible that task would be, but it’s something I’ll try to keep in mind as I go forward.

Anyway, here’s my post that talks about Bin Packing again:]

On to a new chapter! A4- “Storage and Retrieval”

This first one is a classic problem that I guess I haven’t done yet.

The problem: Bin Packing.  This is problem SR1 in the appendix.

The description: Given a finite set U of items, each with a positive integer size, and positive integers B and K.  Can we split U into k disjoint sets such that the sum of the elements in each set is B or less?

Example: Suppose U was {1,2,3,4,5,6}, K=4, and B= 6.  We want 4 disjoint sets that each sum to 6 or less.  For example:

  • {1,5}
  • {2,4}
  • {3}
  • {6}

Note that if K = 3, we would need 3 sets instead of 4, and this wouldn’t be solvable.

The simple reduction: G&J on page 124 say that Bin Packing contains 3-Partition as a special case.  So let’s try reducing from there. Recall the definition of 3-Partition:

Given a set A of 3M elements and an integer B such that the sizes of each element are between B/4 and B/2 and the sum of all of the elements is m*B, can we split A into m disjoint sets that each sum to exactly B?

Keeping in mind that the bounds on the elements in A mean that there are exactly 3 elements in each set in the partition, we can see how this maps easily to the Bin Packing problem:

  • U = A
  • K = m
  • Use the same B

While it is true that the Bin Packing problem allows the sums to be B or less, and the 3-Parittion problem forces the sets to sum to exactly B, the fact that all of the sets have to contain 3 elements and the fact that the sum of all of the element in U is m*B means that if any set in the Bin Packing answer is < B some other set will necessarily be more than B.

Difficulty: 3.  It is basically the same problem, but I think there is enough work needed to justify the reduction that it makes sense as a good easy homework problem.

Numerical 3-Dimensional Matching

SP15 is 3-Parttion.

The next problem is one of G&J’s “unpublished results” problems.  I tried figuring out an elegant way to doing it, but couldn’t make it happen.

The problem: Numerical 3-Dimensional Matching.  This is problem SP16 in the appendix.

The description: Given three sets W, X, and Y, each containing the same amount (m) of elements with positive “sizes” and a positive bound B.  Can we create m sets A1 through Am (containing 3 elements each), such that:

  • Each Ai has exactly one element from W, X, and Y
  • The sum of the sizes of the elements in each Ai is exactly B
  • Each element in W, X and Y is in some Ai

Example: Suppose we have the following sets:

  • W has elements with sizes {1,2,3,4}
  • X has elements with sizes {12,11,7,5}
  • Y has elements with sizes {1,1,4,5}  (the ability to allow repeat numbers is why we define the sets as elements with sizes rather than sets of integers)

If B=14, then the partition where A1 is the first element in W, X, and Y, A2 is the second element in W, X, and Y, and so on gives each Ai set a sum of 14.  Obviously, we don’t need to choose corresponding elements from W, X, and Y to form the sets (for example, rearranging the elements in X to be in increasing order doesn’t change whether the problem can be solved, just the exact composition of the Ai sets)

Reduction: I tried doing a reduction using 3-partition, but got stuck (I’ll show it below, in case you want to try to fix it).  G&J refer you to Theorem 4.4 in the book, which is the proof that 3-partition itself is NP-Complete.

We can follow that along and do similar steps to our problem:

  • Theorem 4.3 shows how to turn 3DM into 4-partition (a problem like 3-partition but each set in the solution has 4 elements instead of 3).  Since the sets that are created in the 4-partition solution come from 4 different places (page 98 calls then a “ui, a wi[·], an xj[·], and a yk[·]).  Since these partitioned sets all add to the same total (B) and come from 4 disjoint parent sets, we can see how we could do basically the same reduction and show that the “numerical 4-dimensional matching problem” is NP-Complete.
  • Theorem 4,4 shows how to turn a 4-parition problem into a 3-partition problem.  The idea is to add enough “pairing” and “filler” elements to the 3-partition instance to make any 4-partition set be split into two 3-partition sets, each consisting of 2 elements from the 4-parittion, plus the “pairing” element of one of the 2 elements chosen.  We can do something similar converting numerical 4-dimensional matching to numerical 3-dimentional matching.  (The difference is that we are given specifically which sets the elements are coming from)  So, if we’re given W, X, Y, and Z in our numerical 4DM instance, we construct W’ to be elements from W and Y, X’ to be elements from X and Z, and Y’ to be the pairing elements of pairs from W’ and X’.  We then need to add enough filler elements to our 3 sets in a similar way to the 3-partition proof (again, the difference is that we have to specifically assign them to W’, X’, or Y’.  But that can be determined by how the 3-partition proof allocates the items)

Difficulty: If you have gone over the 3-partition reduction, this is probably a 6.  Lots of tricky math but doable in a (hard) homework.    But keep in mind you’re tacking it on to the difficulty 8 of understanding the 3-partition reduction in the first place.

My reduction I couldn’t get to work: I really want there to be an easier way to do this.  I tried reducing from 3-partition directly because the problems are so similar.  Here is where I got to:

We’re given a 3-parititon instance S, and an integer B.  Our goal is to split S into sets of size 3 that all add up to B.

So, let’s use S to create 3 sets in our numerical 3DM instance:

  • W has all of the elements in S
  • X has all of the elements in S, but the sizes are each increased by 10B.
  • Y has all of the elements in S, but the sizes are each increased by 100B.

This would make B’ be 111B.

S has a 3-parititon, then for each set {si, sj, sk}, we take the three sets {wi, xj, yk}, {wj, xk, yi}, and {wk, xi, yj}  This will solve the numerical 3DM instance.

My problem comes showing this in the other direction.  If we have a numerical 3DM solution, we can only construct the 3-partition instance if the sets in the 3DM solution arrange themselves nicely like they do above.  I need to show that if the 3DM solution has {wi, xj, yk}, then the set in the 3DM solution that contains wj also contains xi (or xk) and yk (or yi).  I think you can get there by using the rules about how the bounds of the elements in the 3-partition instance work, but the work you need to do to show that it’s true makes this way of doing things no longer “easier” than the Theorem 4.4 proof I sketched above, so I gave up on it.

I still wish there was a more elegant way to transform this problem, though.

Protected: Intersection Graph For Segments On A Grid

This content is password protected. To view it please enter your password below:

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, non-negative integers, and a positive integer K.  Can we find a one-to-one 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:

weighted dimater3

And C= {1,2,2,2,3,5}.  I think the best was you can label this is:

weighted dimater2

The Diameter here is 7 (The length of the path from A-D).

The reduction: G&J say to use 3-Partition, 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 brute-force 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 3-parition 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 > B-x.  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 3-Partition.

Difficulty: 4. G&J does say in the comments that this problem is NP-Complete 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.

Protected: Directed Bandwidth

This content is password protected. To view it please enter your password below:

Protected: 3-Partition

This content is password protected. To view it please enter your password below: