75
Approximation for NP-hard Problems
Approximation
is often used for NP-hard problems …
computing a near-optimal solution
in polynomial time
Examples:
vertex cover of a graph
subset-sum problem
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}