If you need to deal with NP-Hard problems (and you don't feel up to the task of proving that P = NP) you have two basic options:
Approximation Algorithms come with some kind of guarauntee about how close (or far!) from the optimum solution their result will be. Some problems are harder to approximate than others, in the sense that for some problems no polynomial time algorithm gives even a "pretty good" solution ... unless, of course, P = NP. The book includes a section on approximation algorithms. While they are certainly an important subject in theoretical computer science, my opinion is that they are not so important for people who want to solve NP-Hard problems in practice. So I'm going to look at other things.
We're going to first look at techniques for Option 2, and then we'll finish up the course with Option 1.
Example: Consider the travelling salesman problem (TSP) on an undirected, complete graph with positive edge weights. We might choose a starting vertex, v0, call it the "current" vertex, and construct a cycle by continually choosing the vertex from the remaining unchoses vertices that is closest to the "current" vertex, and calling that the new "current" vertex. A totally different greedy algorithm is to keep a set S of edges that will untimately form our cycle, and to continually choose the smallest "good" edge to add to S, where an edge (u,v) is "good" as long as the # edges in S involving u + # edges in S involving v ≤ 1. When no "good" edges remain, the elements of S form a path, and we simply add to S the unique edge that completes our cycle.
Pretty clearly the above example proves that nearest neighbor doesn't always give optimal solutions. Can you find a counter-example for the smallest-edge greedy algorithm?
Randomization and greedy algorithms: Greedy algorithms make choices, of course, but the choices are guided by "heuristics" or rules of thumb. We're not always sure they are the right choices. We can introduce some randomness in how we make our choices and run the resulting greedy algorithm several times, taking the best of the results as our "solution".
Example: Consider the Nearest Neighbor strategy for TSP, which was our first greedy idea above. We could simply choose randomly amongst all neighbors of the "current" vertex that are not already in the cycle. We could incorporate a little randomness into Nearest Neighbor by taking nearest neighor with probability p and choosing randomly from the remaining neighbors with probabilty 1-p, where p is adjustable. Or we could get really tricky and have the probability of choosing neighbor vi be a function of the distance of vi from the "current" vertex. In all cases, if we run the algorithm k times we will very likely have k different answers, and we simply take the best.
Local refinement or local optimization of solutions: Another important idea is to take a solution, usually from a greedy algorithm, and look for ways to improve it. These improvements are usually called "local" refinements, and understanding why means thinking about what we're doing in a different way. We'll talk about that in a little bit. What local refinements you use will be very problem specific, and perhaps even specific to the kind of problem instances your application produces. We'll look at a very well-known local refinement operation for TSP called 2-OPT. The basic idea is simple: You start with a cycle
v0, v1, ..., vn-1. v0and you create a new cycle by deleting edges (vi-1,vi) and (vj,vj+1) and adding edges (vi-1,vj) and (vi,vj+1). Equivalently, you can view this as simply reversing the sub-path vi, ..., vj.
An interesting problem is to find a 2-OPT move (or sequence of 2-OPT moves) to fix the sub-optimal TSP solution produced by the nearest neighbor greedy algorithm on the above example.
Do it all --- combine randomized greedy and local refinement: Finally, we could try combining all our ideas so far: we generate many candidate solutions with a randomized greedy algorithm, use local refinement on until we arrive at a local minimum on each candidate solution, and return the best result we find as our solution. Filling in the gaps in this general approach is tough, though. You need to decide on a randomized greedy algorithm, decide on one or more local refinement operations, and you have to put a lot of thought into implementing these things as efficiently as possible: The faster your algorithms run, the more candidate solutions you can generate and refine, the better your best solution is likely to be.