Source code online books for professionals by professionals

Travelling Salesman Problem.  What’s the complexity class of the best linear programming cutting-plane techniques?  
I couldn’t find it anywhere. Man, the Garfield guy doesn’t have these problems …  (
http://xkcd.com/399
)
But there’s another common version of TSP, where the graph is assumed to be complete. In a complete graph, 
there will always be a Hamilton cycle (if we have at least three nodes), so the reduction doesn’t really work anymore. 
What now? Actually, this isn’t as problematic as it might seem. We can reduce the previous TSP version to the case 
where the graph must be complete by setting the edge weights of the superfluous edges to some very large value. If it’s 
large enough (more than the sum of the other weights), we will find a route through the original edges, if possible.
The TSP problem might seem overly general for many real applications, though. It allows completely arbitrary 
edge weights, while many route planning tasks don’t require such flexibility. For example, planning a route through 
geographical locations or the movement of a robot arm requires only that we can represent distances in Euclidean 
space.
12
 This gives us a lot more information about the problem, which should make it easier to solve—right? Again, 
sorry. No. Showing that Euclidean TSP is NP-hard is a bit involved, but let’s look at a more general version, which is 
still a lot more specific than the general TSP: the metric TSP problem.
A metric is a distance function d(a,b), which measures the distance between two points, a and b. This need not 
be a straight-line, Euclidean distance, though. For example, when working out flight paths, you might want to measure 
distances along geodesics (curved lines along the earth’s surface), and when laying out a circuit board, you might want 
to measure horizontal and vertical distance separately, adding the two (resulting in so-called Manhattan distance 
or taxicab distance). There are plenty of other distances (or distance-like functions) that qualify as metrics. The 
requirements are that they be symmetric, non-negative real-valued functions that yield a distance of zero only from 
a point to itself. Also, they need to follow the triangular inequality: d(a,c) £ d(a,b) + d(b,c). This just means that the 
shortest distance between two points is given directly by the metric—you can’t find a shortcut by going through some 
other points.
Showing that this is still NP-hard isn’t too difficult. We can reduce from the Hamilton cycle problem. Because of 
the triangular inequality, our graph has to be complete.
13
 Still, we can let the original edges get a weight of one, and 
the added edges, a weight of, say, two (still doesn’t break things). The metric TSP problem will give us a minimum-
weight Hamilton cycle of our metric graph. Because such a cycle always consists of the same number of edges (one 
per node), it will consist of the original (unit-weight) edges if and only if there is a Hamilton cycle in the original, 
arbitrary graph.
Even though the metric TSP problem is also NP-hard, you will see in the next section that it differs from the 
general TSP problem in a very important way: We have polynomial approximation algorithms for the metric case, 
while approximating general TSP is itself an NP-hard problem.
12
Unless we want to take relativity or the curvature of the earth into account ...
13
Any infinite distances would break it, unless it was completely without edges or consisted of only two nodes.

---

Chapter 11 
■
 hard problems and (lImIted) sloppIness
245
When the Going Gets Tough, the Smart Get Sloppy
As promised, after showing you that a lot of rather innocent-looking problems are actually unimaginably hard, I’m 
going to show you a way out: sloppiness. I mentioned earlier the idea of “the instability of hardness,” that even small 
tweaks to the problem requirements can take you from utterly horrible to pretty nice. There are many kinds of tweaks 
you can do—I’m going to cover only two. In this section, I’ll show you what happens if you allow a certain percentage 
of sloppiness in your search for optimality; in the next section, we’ll have a look at the “fingers crossed” school of 
algorithm design.
Let me first clarify the idea of approximation. Basically, we’ll be allowing the algorithm to find a solution that may 
not be optimal, but whose value is at most a given percentage off. More commonly, this percentage is given as a factor, 
or approximation ratio. For example, for a ratio of 2, a minimization algorithm would guarantee us a solution at most 
twice the optimum, while a maximization problem would give us one at least half the optimum.
14
 Let’s see how this 
works, by returning to a promise I made back in Chapter 7.
What I said was that the unbounded integer knapsack problem can be approximated to within a factor of two 
using greed. As for exact greedy algorithms, designing the solution here is trivial (just use the same greedy approach 
as for fractional knapsack); the problem is showing that it’s correct. How can it be that, if we keep adding the item 
type with the highest unit value (that is, value-to-weight ratio), we’re guaranteed to achieve at least half the optimum 
value? How on Earth can we know this when we have no idea what the optimum value is?
This is the crucial point of approximation algorithms. We don’t know the exact ratio of the approximation 
to the optimum—we give only a guarantee for how bad it can get. This means that if we get an estimate on how