CS Degree Day 62

What I did today?

• Lecture 9: More NP-complete reductions - Hamiltonian path, subset sum
• Lecture 10: Approximation algorithms - vertex cover, TSP approximation

Approximation algorithms are a pragmatic response to NP-hardness. If we cannot solve optimally in polynomial time, can we solve within a factor of optimal? For vertex cover: yes, factor 2. For TSP with the triangle inequality: yes, factor 1.5 (Christofides). These guarantees feel like engineering rather than mathematics, and I mean that as a compliment.