Stack Overflow
Stack Overflow

1-approximation
321
reputation
1
4
13
  • Member since December 30 2015
  • 23 profile views
  • Last seen Jun 21 '16 at 20:13

Rule: I always upvote

Theorem:

Given a problem Prob and an algorithm Algo that solves Prob. If Algo is a 1-approximation algorithm then Algo gives the optimal solution for Prob.

If Prob is an NP-hard problem and Algo is a polynomial-time algorithm, then P=NP.

Proof: The proof is omitted due to space limitation.