Approximation of NP-hard combinatorial optimization problems Approximation ratio Relate to the optimum Related to the optimum of a relaxed problem Round the optimum of a relaxed problem Basic techniques Rounding techniques Example: vertex cover Solve a fractional relaxation Feasibility How good is a relaxation? Integrality gap for the relaxation of vertex cover Primal-dual schema Dual formulation An r-approximation alg. if Primal-dual schema for vertex cover Algorithm Analysis Conclusions
