Citation Youtube Harvard University

Approximation algorithms via dual fitting (wrap-up), LP integrality gaps, definitions of PTAS/FPTAS/FPRAS, PTAS for knapsack.

Finish the approximate algorithm via dual fitting.

LP Integrity Gaps

Poly time approximation schemes. PTAS FPTAS FPRAS

Theorom Greedy is a log n approximation.

There's n sets; the cost is a set of S. Sets put in []

The goal is to find a subset of the input sets.

Goal is to cover all of [n] with a minimal cost.

In computer science and operations research, approximation algorithms are efficient algorithms finding approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution compared to the optimal one.