1. LB + Fix
Start from some Lower Bound which might not be feasible and then fix it by doing something (for example, add some edges).
Examples: Vertex Cover (2), TSP (1.5), Steiner tree (2), Shortest superstring (4) -- use min weight cycle cover as LB and fix it using simple concatenation (one shot).
2. Incremental Algorithms.
This includes all algorithms that keep adding something to the optimal solution. A greedy algorithm is a commonly used. Most algorithm in this framework start from scratch but we might also start from some lower bound.
Example: Set Cover ($H_n$).
3. Search on all (polynomial) choices
Consider some possible solutions and ways of obtaining solution. Argue that one of these would be "good".
- Search for Optimality: Argue that one of these choices is within the desired approximation factor. Example: Item pricing?
- Search for Feasibility: Make sure all these choices are in the desired approximation factor. However, they might not be all feasible. Argue that one of them is. Example: k-server -- keep adding edges to the graph and argue that once OPT is obtained, a feasible solution is also obtained.
4. Divide and Conquer
Algorithms in this framework splits the given instance into many parts and solve each part "locally." Usually we can combine the solution back easily, but it might be tricky sometimes.
- Local Structure For example, split a graph into several components. Example: Multiway cut where we find optimal solution for each vertex and combine them.
- Local Ratio (Layering in VV's book) This is kind of weird way to split an instance -- split by weights. Example: Feedback vertex set -- put water in each vertex proportional to its "cyclomatic" number until some vertex's weight is "tighten". Repeat on the rest. For each of this substructure, show that it's easy to be 2-approximated.
- Adaptive Local Ratio.
List of Problems & Simple Algorithms
- Scheduling (in Handbook) 2-1/m. Open: Can do better than 2-1/m ?