Next: Vertex Cover Up: approx-algo9 Previous: -approximation
Linear programming is an extremely versatile technique for designing approximation algorithms, because it is one of the most general and expressive problems that we know how to solve in polynomial time. In this section we will discuss some applications of linear programming to the design and analysis of approximation algorithms.