Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
90
reputation
8

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.

1
answer
4
questions
~5k
people reached
  • Member for 3 years, 9 months
  • 4 profile views
  • Last seen Jan 17 '17 at 21:48

Top tags (5)

Score 2
Posts 3
Score 2
Posts 2
Score 2
Posts 2
Score 0
Posts 1
Score 0
Posts 1

Top posts (5) All Questions Answers | Votes Newest

Badges (8)

Gold

Silver

Bronze

8

Rarest