138
reputation
1
13

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
~2k
people reached
  • Member for 3 years, 5 months
  • 20 profile views
  • Last seen Jan 17 '17 at 21:46

Top tags (9)

Score 3
Posts 6
Posts % 55
Score 3
Posts 4
Score 3
Posts 4
Score 0
Posts 3
Score 0
Posts 2
Score 0
Posts 2

Top posts (11) All Questions Answers | Votes Newest

View all questions and answers

Badges (14)

Gold

Silver

1

Rarest

Bronze

13

Rarest