Source code online books for professionals by professionals

good the optimum can get, we can work with that instead of the actual optimum, and our answer will still be valid. 
Let’s consider the maximization case. If we know that the optimum will never be greater than A and we know our 
approximation will never be smaller than B, we can be certain that the ratio of the two will never be greater than A/B.
15
For the unbounded knapsack, can you think of some upper limit to the value you can achieve? Well, we can’t 
get anything better than filling the knapsack to the brim with the item type with the highest unit value (sort of like an 
unbounded fractional solution). Such a solution might very well be impossible, but we certainly can’t do better.  
Let this optimistic bound be A.
Can we give a lower bound B for our approximation, or at least say something about the ratio A/B? Consider 
the first item you add. Let’s say it uses up more than half the capacity. This means we can’t add any more of this 
type, so we’re already worse off than the hypothetical A. But we did fill at least half the knapsack with the best item 
type, so even if we stop right now, we know that A/B is at most 2. If we manage to add more items, the situation can 
only improve.
What if the first item didn’t use more than half the capacity?
16
 Good news, everyone: We can add another item of 
the same kind! In fact, we can keep adding items of this kind until we’ve used at least half the capacity, ensuring that 
the bound on the approximation ratio still holds.
There are tons and tons of approximation algorithms out there—with plenty of books about this topic alone.  
If you want to learn more about the topic, I suggest getting one of those (both The Design of Approximation Algorithms 
by Williamson and Shmoys and Approximation Algorithms by Vijay V. Vazirany are excellent choices). I will show you 
one particularly pretty algorithm, though, for approximating the metric TSP problem.
What we’re going to do is, once again, to find some kind of invalid, optimistic solution and then tweak that until 
we get a valid (but probably not optimal) solution. More specifically, we’re going to aim for something (not necessarily 
a valid Hamilton cycle) that has a weight of at most twice the optimum solution and then tweak and repair that 
something using shortcuts (which the triangle inequality guarantees won’t make things worse), until we actually get a 
Hamilton cycle. That cycle will then also be at most twice the length of the optimum. Sounds like a plan, no?
14
Note that we always divide the larger of the two (optimum and approximation) by the smaller.
15
For the minimization case, just reverse the logic, and consider the ratio B/A.
16
Notice the use of “proof by cases” here. It’s a really useful technique.

---

Chapter 11 
■
 hard problems and (lImIted) sloppIness
246
What, though, would be only a few shortcuts away from a Hamilton cycle and yet be at most twice the length of 
the optimum solution? We can start with something simpler: What’s guaranteed to have a weight that is no greater 
than the shortest Hamilton cycle? Something we know how to find? A minimum spanning tree! Just think about it. 
A Hamilton cycle connects all nodes, and the absolutely cheapest way of connecting all nodes is using a minimum 
spanning tree.
A tree is not a cycle, though. The idea of the TSP problem is that we’re going to visit every node, walking from 
one to the next. We could certainly visit every node following the edges of a tree, as well. That’s exactly what Trémaux 
might do, if he were a salesman (see Chapter 5).
17
 In other words, we could follow the edges in a depth-first manner, 
backtracking to get to other nodes. This gives us a closed walk of the graph but not a cycle (because we’re revisiting 
nodes and edges). Consider the weight of this closed walk, though. We’re walking along each edge exactly twice, so it’s 
twice the weight of the spanning tree. Let this be our optimistic (yet invalid) solution.
The great thing about the metric case is that we can skip the backtracking and take shortcuts. Instead of going 
back along edges we’ve already seen, visiting nodes we’ve already passed through, we can simply make a beeline for 
the next unvisited node. Because of the triangular inequality, we’re guaranteed that this won’t degrade our solution, 
so we end up with an approximation ratio bound of two! (This algorithm is often called the “twice around the tree” 
algorithm, although you could argue that the name doesn’t really make that much sense because we’re going around 
the tree only once.)
Implementing this algorithm might not seem entirely straightforward. It kinda is, actually. Once we have our 
spanning tree, all we need is to traverse it and avoid visiting nodes more than once. Just reporting the nodes as they’re 
discovered during a DFS would actually give us the kind of solution we want. You can find an implementation of this 
algorithm in Listing 11-1. You can find the implementation of prim in Listing 7-5.