Source code online books for professionals by professionals

i
. We could then have a capacity of 2
1
 + … + 2
n
, and run our maximization. This isn’t quite enough, 
though; the maximization wouldn’t care if we have one instance of 2
n
 or two instances of 2
n–1
. We can add another 
constraint: We represent number i by 2
i
 + 2
n+1
 and set the capacity to 2
1
 + … + 2
n
 + n2
n+1
. For the maximization, it 
will still pay to fill every slot from 1 to n, but now it can include only n occurrences of 2
n+1
, so a single instance of 
2n will be preferable to two instances of 2
n–1
. But we’re not done yet … this only lets us force the maximization to 
take exactly one of each number, and that’s not really what we want. Instead, we want two versions of each item, 
one representing that the number is included and one representing that it is excluded. If number i is included, we 
will add w
i
, and if it is excluded, we will add 0. We will also have a the original capacity, k. These constraints are 
subordinate to the “one item per slot” stuff, so we’d really like to have two “digits” in our representation. We can 
do that by multiplying the slot constraint number by a huge constant. If the largest of our numbers is B, we can 
multiply the constraints with nB, and we should be on the safe side. The resulting scheme, then, is to represent 
number w
i
 from the original problem by the following two new numbers, representing inclusion and exclusion, 
respectively: (2
n+1
 + 2
i
)nB + w
i
 and (2
n+1
 + 2i)nB. The capacity becomes (n2
n+1
 + 2
n
 + … + 2
1
)nB + k.
11-6. It’s easy to reduce three-coloring to any k-coloring for k > 3; you simply conflate two or more of the colors.
11-7. Here you can reduce from any number of things. A simple example would be to use subgraph isomorphisms to 
detect cliques.
11-8. You can simply simulate undirected edges by adding directed ones in both directions (antiparallel edges).
11-9. You can still use the red-green-blue scheme to simulate direction here and then use the previous reduction 
from directed Hamilton cycle to directed Hamilton path (you should verify how and why this would still work). Here’s 
another option, though. Consider how to reduce the undirected Hamilton cycle problem to the undirected Hamilton 
path problem. Choose some node u, and add three new nodes, u’, v and v’, as well as the (undirected) edges (v,v’) and 
(u,u’). Now add an edge between v and every neighbor of u. If the original graph has a Hamilton cycle, this new one 
will obviously have a Hamilton path (just disconnect u from one of its neighbors in the cycle, and add u’ and v’ at 
either end). More importantly, the implication works both ways: A Hamilton path in the new graph must have u’ and 
v’ as its end points. If we remove u’, v, and v’, we’re left with a Hamilton path from u to a neighbor of u, and we can link 
them up to get a Hamilton cycle.
11-10. This is (unsurprisingly) sort of the opposite of the reduction in the other direction. Instead of splitting an 
existing node, you can add a new one. Connect this node to every other. You will then have a Hamilton cycle in the 
new graph if and only if there is a Hamilton path in the original one.

---

Appendix d 
■
 Hints for exercises
286
11-11. We can trace things up the chain. Longest paths in DAGs can be used to find Hamilton paths, but only in DAGs. 
This will, again, let us find directed Hamilton cycles in digraphs that become DAGs when we split them at a single 
node (or, by fiddling with the reduction, something very close to that). However, the digraph we used for reducing 
3-SAT to the directed Hamilton cycle was nothing like this. True, we could see a hint of this structure in the s and t 
nodes, and the general downward direction of edges from s to t, but every row was full of antiparallel edges, and the 
ability to go in either direction was crucial to the proof. Therefore, things break down here if we assume acyclicity 
further down.
11-12. The reasoning here is quite similar to that in Exercise 11-11.
11-13. As discussed in the main text, if the object is bigger than half the knapsack, we’re done. If it’s slightly less 
(but not as small as a quarter of the knapsack), we can include two and again have filled more than half. The only 
remaining case is if it’s even smaller. In either case, we can just keep piling on, until we get past the midline—and 
because the objects is so small, it won’t extend far enough across the midline to get us into trouble.
11-14. This is actually easy. First, randomly order the nodes. This will give you two DAGs, consisting of the edges 
going left-to-right and those going right-to-left. The largest of these must consist of at least half the edges, giving you a 
2-approximation.
11-15. Let’s say all the nodes are of odd degree (which will give the matching as large a weight as possible). That 
means the cycle will consist only of these nodes, and every second edge of the cycle will be part of the matching. 
Because we’re choosing the minimum matching, we of course choose the smallest of the two possible alternating 
sequences, ensuring that the weight is at most half the total of the cycle. Because we know the triangle inequality 
holds, relaxing our assumption and dropping some nodes won’t make the cycle—or the matching—more expensive.
11-16. Feel free to be creative here. You could, perhaps, just try to add each of the objects individually, or you could 
add some random objects? Or you could run the greedy bound initially—although that will happen already in one of 
the first expansions …
11-17. Intuitively, you’re getting the most possible value out of the items. See whether you can come up with a more 
convincing proof, though.
11-18. This requires some knowledge of probability theory, but it’s not that hard. Let’s look at a single clause, where 
each literal (either a variable or its negation) is either true or false, and the probability of either outcome is 1/2. This 
means that the probability of the entire clause being true is 1–(1/2)
3
 = 7/8. This is also the expected number of clauses 
that will be true, if we have only a single clause. If we have m clauses, we can expect to have 7m/8 true clauses. We 
know that m is an upper bound on the optimum, so our approximation ratio becomes m/(7m/8) = 8/7. Pretty neat, 
don’t you think?
11-19. The problem is now expressive enough to solve (for example) the maximum independent set problem, which is 
NP-hard. Therefore, your problem is also NP-hard. One reduction goes as follows: Set the compatibility for each guest 
to 1 and add conflicts for each edge in the original graph. If you can now maximize the compatibility sum without 
inviting guests who dislike each other, you have found the largest independent set.
11-20. The NP-hardness can easily be established, even for m = 2, by reducing from the partition problem. If we can 
distribute the jobs so that the machines finish at the same time, that will clearly minimize the completion time—and 
if we can minimize the completion time, we will also know whether they can finish simultaneously (that is, whether 
the values can be partitioned). The approximation algorithm is easy, too. We consider each job in turn (in some 
arbitrary order) and assign it to the machine that currently has the earliest finish time (that is, the lowest workload). 
In other words, it’s a straightforward greedy approach. Showing that it’s a 2-approximation is a little bit harder. Let