Lecture Notes for CS 512, Algorithm Design

27 March 1999, Bounded Approximation Algorithms

1. the vertex cover set

   1. the vertex cover C of an undirected graph G is a subset of G.V such that every edge in G.E has at least one vertex in C

   2. the vertex-cover problem finds the smallest vertex cover of a given graph.

   3. a straight-forward, exhaustive search through all subsets of G.V

   4. is there a tractable algorithm for vertex cover - it's NP-complete.

2. find tractable algorithms producing near-optimal results.

   1. forget minimality

   2. pick edges at random from G.E and add the vertices to the vertex cover; remove other edges sharing the vertices added

   3. is it sub-optimal

   4. how badly is it sub-optimal

3. what does "near optimal" mean - the ratio bound

4. for maximization problems C <= C_O

5. for minimization problems C_O <= C

6. max(C_O/C, C/C_O) is the measure of suboptimality

7. bound max(C_O/C, C/C_O) from above by r(n)

8. fixed ratio bound r independent of n.

9. relative error bound e(n) >= |C - C_O|/C_O

10. approximation schemes take a problem instance and an error bound e

11. polynomial-time approximation scheme achieves an error bound of e in time polynomial in n.

12. fully polynomial-time approximation algorithms

13. some comments about approximation algoritms

    1. don't make them too simple -

    2. don't make them too complex -

    3. postprocess sub-optimal results to improve them -

    4. some algorithms don't approximate - bandwidth reduction

This page last modified on 1 April 2000.