15: Approximation Algorithms

Coming soon.

Topics

• Approximation ratios
• Vertex cover (2-approximation)
• Set cover (greedy, log n)
• Traveling salesman (metric TSP)
• PTAS and FPTAS
• Inapproximability results