1-approximation
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.
2
answers
9
questions
~3k
people reached
-
Member for 5 years
-
24 profile views
-
Last seen Jan 17 '17 at 21:46
Communities (15)
Top network posts
Badges (15)
Gold
—
Silver
2
Rarest
-
Mar 13 '16
-
Nov 13 '19
Bronze
13
Rarest
-
Mar 1 '16
-
Feb 21 '16
-
Feb 21 '16