Approximation Algorithms

If it costs too much to get the exact answer, maybe we can get close enough.

Motivation

Many "optimization" problems (e.g. vertex cover, traveling salesperson, etc.) are NP-complete or run in provably exponential time. An approximation algorithm is one that runs in polynomial time and gives an answer which is close to, but not quite, optimal.

Generally we want these solutions to both run quickly and have some kind of guaranteed error bound (e.g. "within 5% of the optimal value").

Two Examples

Vertex Cover

This algorithm gets you a decent approximation

    Set result = { };
    while (g.numberOfEdges() > 0) {
        Node n = the node with the largest degree in g;
        g.removeNode(n);
        result.add(n);
    }
    return result;

It fails on

ygraph.png

giving an answer of cardinality 4 instead of 3.

Exercise: Actually implement this algorithm. Fix it up so it doesn't destroy the input graph (you can run it on a copy of the input graph, or use some other techniques).

Chromatic Number

A good approximation is: don't backtrack. This fails to give an optimal answer on:

cnapprox.png

More

Wikipedia has an article on approximation algorithms with links to textbooks, articles and other online sources.