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").
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
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).
A good approximation is: don't backtrack. This fails to give an optimal answer on:
Wikipedia has an article on approximation algorithms with links to textbooks, articles and other online sources.