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.