87
Approximation for Problems in NP
Approximation
is often used for problems in NP…
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}