Vincec's Dimension

Algorithm Review Notes - Approximation Algorithms

Word count: 304 / Reading time: 2 min
2018/11/26 Share

Approximation algorithm

An algorithm that returns near-optimal solutions is called an approximation algorithm

a-approximation algorithm

Let Opt(I) is the optimal solution, Alg(I) is the result of a approximation algorithm.

  • For Minimization Problem, Alg(I) ≤ a*Opt(I), for some a > 1, Alg(I) will be between Opt and a*Opt.
  • For Maximization Problem, Alg(I) ≥ a*Opt(I), for some 0 < a < 1, Alg(I) will be between Opt and a*Opt.

Graph Coloring

Greedy Approximation

  • Find the verices with the highest degree
  • Color the first vertex with color 1
  • Color every vertex that not adjacent to it with color 1
  • Remove all colored vertices from the list
  • Repeat

Vertex Cover

To find the smallests set of vertex in V

Greedy 2-Approximation

  • If there is a edge
  • Find two vertices in the finded arbitrary edge, as (u, v)
  • Vertex Cover Unit the (u, v), #adding the two vertices in the cover set.
  • Remove every edges that connect with u or v
  • Repeat until there is no edge
  • (keep looking the single edge and make it seprated from the original G)

Proof

  • Alg(I) = 2 * Maximal matching on G
  • Matching ≤ Opt(I)
  • Alg(I) ≤ 2 * Opt(I)

Traveling Salesman Problem

Greedy 2-Approximation

  • Find a MST of G
  • Greate a cycle by doubling edges
  • Remove double visited edges

Proof
Alg(I) ≤ 2 |MST| ≤ 2 Opt(I)

Christofides Alg - 3/2-Approximation
Only add edges between the odd degree vertices, skip the even degree vertices.

General TSP

Set Covering Problem

Greedy ln(n)-Approximation

  • Find the subset Sk covers the most elements
  • Update the already covered set
  • Add Sk into the Final Result set
  • Repeat until there is no uncovered set

Load Balancing

Greedy 2-Approximation
Assign job j to machine i whose load Li is smallest - O(nlogn)

Reference

  • Slides
CATALOG
  1. 1. Approximation algorithm
    1. 1.1. a-approximation algorithm
  2. 2. Graph Coloring
  3. 3. Vertex Cover
  4. 4. Traveling Salesman Problem
    1. 4.1. General TSP
  5. 5. Set Covering Problem
  6. 6. Load Balancing
  7. 7. Reference