Tag Archives: No G&J reference

Capacity Assignment

This problem is from the same “unpublished manuscript” as last week’s.

The problem: Capacity Assignment.  This is problem SR7 in the appendix.

The description: Given a set C of “communication links”, and set M of positive capacities.  Each pair of a link c and a capacity m also has a cost function g(c,m) and delay penalty d(c,m) that has the following properties:

  • If i < j ∈ M, then g(c,i) ≤ g(c,j)
  • If i < j ∈ M, then d(c,i) ≥ d(c,j)

We’re also given positive integers K and J.  The problem is: Can we assign a capacity to each link such that the total g cost of all of our assignments is ≤ K and the total d cost of all of our assignments is ≤ J?

Example: There’s a lot to parse in that problem description.  The first thing to notice is that the set of links C doesn’t necessarily have to link anything together (it’s not like it has to apply to an underlying graph).  So we can just give them names:

C={a,b,c,d,e}

Next, there is no reason why the set of capacities has to be assigned as a bijection to C- the set M could be a different size entirely than the size of C:

M={1,2}

The cost function has to have the property that if we assign a 2 to a link, it has to cost as least as much as assigning 1 to the link:

g(c,1) = 3 for all c

g(c,2) = 4 for all c

The delay function has to have the property that if we assign a higher capacity to a link, the delay can’t be larger than assigning a lower capacity:

d(c,1) = 6 for all c

d(c,2) = 5 for all c

In this case, if we assign the capacity of 1 to all links, we get a total cost of 15 and a total delay of 30.  If we assign the capacity of 2 to all links, we get a total cost of 20 and a total delay of 25.     If we have K = 18, and J = 27, we can achieve that by setting 2 links to have capacity 1 and 3 links to have capacity 2.

The reduction: The example above is pretty close to how the reduction will work.  We will reduce from Sum of Subsets, so we start with a set S of integers and a target B.   Our set C will have one element for each element in S.  Our set M will be {1,2}.  Assigning a capacity of 1 will imply we don’t want to take this element in S’, and assigning a capacity of 2 will imply that we do.  (This makes more sense if I can use the set {0,1} for M, but the problem description says the elements of M have to be positive)

We will define our g function so that g(c,1) = 1 for all c, and g(c,2) will be s(c)+1 (where s(c) is the size of the element in S that corresponds to c).

Our d function will work similarly:  d(c,1) = s(c)+1 for all c, and d(c,2) = 1 for all c.  These functions both follow the restrictions for how g and d work.

Set K = |S| + B.  Since each cost is either s(c)+1 or 1, this is saying that there needs to be enough elements assigned a 1 (such that its cost is 1, instead of s(c)+1) to that the sizes of those elements does not exceed K.

Let T = The sum of all of the sizes of all of the elements in S.  Then let J = |S| + T – B.  Again, each d value always includes 1, and may include s(c) as well.  So this is saying that there needs to be enough values assigned a 2 (so that its delay is 1) so that the sizes of those elements does not exceed J.

If S has a SOS solution S’, then assigning a capacity of 2 to all elements in S’ and a 1 to all elements in S’ gives us a cost value of exactly K, and a delay value of exactly J.

If we have a Capacity Assignment solution, then notice that K+J = 2|S|  + T, and so is the sum of all delays and capacities no matter what assignment is chosen.  (g(c,m) + d(c,m) = s(c)+2, for all c, no matter what m we use).  So if the sum of the delays (or costs) were strictly less than K, the sum of the costs (or delays) would have to be strictly more than J.  The only way to satisfy both the K and J constraints is to make the sums exactly equal, which gives us a SOS solution.

Difficulty: 4.  I think the algebra for this problem is a little easier than last week’s, but it does take some work to understand what the problem is asking.  Changing the problem slightly to allow assignments and costs and delays to be 0 instead of making them all be positive integers makes the reduction easier too.

Multiple Copy File Allocation

These next two problems are from an “unpublished manuscript” that I can’t find.  Assuming I did them correctly, I think they are also good problems for students to work on.

The problem: Multiple Copy File Allocation.  This is problem SR6 in the appendix.

The description: Given a graph G=(V,E), where each vertex v ∈ V has a “usage” u(v), and a “storage cost” s(v) (both positive integers), and a positive integer K.  Can we find a subset V’ of V where for each v ∈ V we define d(v) to be the length of the shortest path from v to some member of V’, that the sum of:

  • The s(v) values for all vertices in V’ plus
  • The d(v)*u(v) values for all vertices not in V’ is ≤ K?

Example: The idea is that each vertex in V’ pays its s(v) cost, and each vertex not in V’ pays its u(v) cost for each edge is has to go through to get to something in V’.  Here’s a simple example:

sr6

Each node lists its s value first and u value second.  If we take just the “1,10” node into V’, our total cost is:

  • 1 from the “1,10” node (its s value)
  • 2 + 3 + 4 from each of its neighbors (their u values * a distance of 1)
  • 2 from the “90,1” vertex.  (u cost of 1, times a distance of 2 edges from the vertex in V’)

..for a total of 12.  I think that’s minimal.

Reduction: G&J say to use  Vertex Cover, and mention that we can make all s values equal to each other and all u values equal to each other.  The phrasing implies that we shouldn’t make the s value and u values the same altogether, which is a good hint.

So we start with out VC instance: a graph G=(V,E) and an integer K.  We will use the same graph.  Let s = the s(v) for each vertex = |V|.  Let u = the u(v) for each vertex =  \lceil|V|/2 \rceil + 1 (The smallest integer larger than |V|/2).

Set K’ = K*s + (|V|-K)* u.  Hopefully it’s clear how this number will allow a solution to the VC problem take that cover and create a solution to the MCFA problem.

If we have a MFCA solution, first notice that any vertices that are 2 (or more) edges away from something in V’ are contributing 2*u to the total cost.  Since 2*u > s, we can add a vertex to V’ at a distance 1 away from these distant vertices and keep our total cost ≤ K’.  This means we can transform any MCFA solution into one that is also a solution but where V’ is a cover of V.

Also notice that even after making these changes that if we were to have K+1 (or more) vertices in V’, our total cost would be (K+1)*s + (|V|-K-1)* u.  This is more than K’ (it adds an extra s of cost |V| and removes a u of cost |V|/2+1).

So, we can construct a MCFA solution where there are K or less vertices in V’ that form a cover.  This gives us a solution to the VC instance.

Difficulty: 5.  It takes a little playing around with the algebra to get the correct values, but the idea that we can make the s and u values the same for all vertices is helpful, and gives a clear path to how you’d reduce this problem from VC.

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

Ratio Clique

Last week it was pointed out to me that my reduction for Balanced Complete Bipartite Subgraph was wrong, and in my searches to fix it, I found that the real reduction (by Johnson) used a variant of Clique that said (without proof)) that Clique is NP-Complete even if K was fixed to be |V|/2.  I looked up the Clique problem in G&J, and they say in the comments that it is NP-Complete for K = any fixed ratio of V.

I thought this was a neat easy problem that fit in the 3-6 difficulty range I mentioned last week and decided it was worth a post.  But thinking about this brings up some subtle issues relating to ratios and constants that are common sources of errors among students.  I’ll talk about that at the end.

The problem: I don’t know if there is an official name, so I’m calling it “Ratio Clique”.  It is mentioned in the comments to GT19 (Clique).

The description: For any fixed number r, 0< r < 1, does G have a clique of size r*|V| or more?

Example:  Here’s a graph we’ve used for a previous problem:

maximum fixed-length disjoint paths

If r = .5, then r*|V| = 3.5.  So we’re asking if a clique of 3.5 or more vertices exists (which really means a clique of 4 or more vertices).  It does not exist in this graph.  If r ≤ \frac{3}{7}, then we would be looking for a clique of size 3, which does exist in this graph (vertices b, c, and t)

The reduction: We will be reducing from the regular Clique problem.  Since we want to show this “for any fixed value of r”, we can’t change r inside our reduction.

So we’re given a graph G=(V, E) and a K as our instance of Clique. We need to build a graph G’=(V’, E’) that has a fixed K’ = ⌈r*|V’|⌉.

G’ will start with G, and will add new vertices to the graph.  The vertices we add depend on the ratio s of K to |V|    (K = ⌈s*|V|⌉).  K’ is initially K, but may change as vertices are added to the graph.

If r > s, then we need to add vertices to V’ that will connect to each other vertex in V’, and will increase K’ by 1.  This increases the ratio of \frac{K'}{|V'|}, and we keep adding vertices until that ratio is at least r.

If G has a clique of size K, then the extra vertices in K’ can be added to the clique to form a larger clique (since these new vertices connect to every other vertex)

If G’ has a clique of size K’, notice that it must contain at least K vertices that were initially in G. (We only added K’-K new vertices).  These vertices that exist in G are all connected to each other and so will form a clique in G.

If r < s, then we will add vertices to V’ that are isolated (have no edges connecting to them).  K’ will stay equal to K.  Each vertex we add will reduce the ratio of \frac{K'}{|V'|}, and we keep adding vertices until  K=⌈r*|V’|⌉.

Since these new vertices can not be part of any clique in G’, any clique in G’ must consist only of vertices from G.  Since K=K’, this gives us a clique of size K in both graphs.

It is probably also worth mentioning just how many vertices need to get added to the graph in each case, to make sure that we are adding a polynomial number.  If r>s, we will be adding w vertices to satisfy the equation: ⌈s*|V|⌉ + w = ⌈r*(|V|+w)⌉

(These are both ways of expressing K’)

Dropping the ceiling function (since it only leads to a difference of at most one vertex) Solving for w gets us w = \frac{(s|V|-r|V|)}{(r-1)}.  Since r > s, both sides of that division are negative, so w ends up being positive, and polynomial in |V|.

If r < s, we will be adding w vertices to satisfy the equation:

⌈s*|V|⌉ = ⌈r(|V|+w)⌉

(These are both ways of expressing K)

This can similarly be solved to w = s|V|-r|V|.  Since s > v, this is also a positive (and polynomial) number of new vertices.

A possible source of mistakes: I’m pretty sure this reduction works, but we need to be careful that there is a difference between “for any fixed ratio r of |V|” and “for any fixed K”.  Because for a fixed K (say, K=7) solving the “Does this graph have a 7-Clique?” problem can be solved in polynomial (by enumerating all subgraphs of size 7, for example.  There are n \choose 7 subgraphs, which is O(N^7)).  By choosing a ratio instead of a constant K, we gain the ability to scale the size of K’ along with the size of the graph and avoid this issue.  But it is worth mentioning this to students as a possible pitfall.  It’s very easy to do things in a way that effectively is treating r|V| as a constant K, which won’t work.

Difficulty: 3, but if you’re going to make students to the algebra to show the number of vertices that are added, bump it up to a 4.

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 Matching With Target Sums

In an effort to make my semesters easier, during breaks I do most of the research on the problems and write quick sketches of the reductions out.  This way when I get to the weekly post, most of the hard math work is done, and I don’t get surprised by a super hard problem.

(I’m doing something similar over our winter break at the present.  I’ve  got sketches up through the middle of April, and I’m currently working on problem SR13- “Sparse Matrix Compression”- which is an “unpublished manuscript”  problem that I’m having a lot of trouble with.  Keep your fingers crossed).

Anyway, I was looking through my notes today and I realized that I’d skipped this problem!  Luckily, I think the reduction is pretty easy.

The problem: Numerical Matching With Target Sums.  This is problem SP17 in the appendix.

The description: Given two sets X and Y, each with the same number (m) of elements, and each with a positive integer size.  We’re also given a “target vector” V, also of M elements, consisting of positive integer entities.  Can we create m sets A1 through Am such that:

  • Each Ai has one element from X and one element from Y
  • Each element in X and Y appears exactly once in some Ai
  • The sum of the sizes of the elements in each Ai is exactly Bi?

Example: I’ll use an example derived from last week’s Numerical 3-Dimensional Matching example because I think it will illustrate how the reduction will work:

  • X = {12,11,7,5}
  • Y = {1,1,4,5}
  • B = {13,12,11,10}

(W from last week was {1,2,3,4}, and B was 14.)

Letting A1 be the first elements of X and Y, A2 being the second elements of X and Y, and so on down, gives us a solution.

Reduction: G&J say to use Numerical 3-Dimensional Matching, and don’t even bother to mark it as “unpublished results”, probably because they think it’s so easy.

Our Numerical 3DM instance is three sets: W, X, and Y, and a bound B.  We need 2 sets and a “bound vector” for the instance of the Numerical Matching problem.  So what we do is:

  • X’ = X
  • Y’ = Y
  • Each bi in the B vector will be set to B-wi.  This is the amount we need the element from X and Y to add up to, so that when we add in the element from W, we get B.

If we have a solution to the Numerical 3-Dimensional Matching solution, then each Ai in that solution consists of 3 elements: wi, xj and yk that sum to B.  Then in our Numerical Matching With target Sums instance, we have a set Ai‘ where xj + yk sum to B-wi.  The same is true in the reverse direction.

Difficulty: 3, which may be too high.  I can see people getting confused by the fact that the sets in the 3DM instance can be taken in any order, but the B vector in the Target Sum matching problem needs to have Ai‘s element sum exactly to bi, and wondering how to force the correct W element to be in that spot?

(The answer is that you define it when you build B.  We set b1 to be “the sum that works when you use wi“, so it (or something with the exact same size, so we can swap the elements) has to go in that position in the vector).

Protected: 3-Matroid Intersection

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

Protected: Minimum Separating Set

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

Protected: Minimum Test Set

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

Protected: Minimum Broadcast Time

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