Computer Science
Meta user
Network profile
318
reputation
2
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
~3k
people reached
  • Member for 4 years, 1 month
  • 22 profile views
  • Last seen Jan 17 '17 at 21:46

Communities (15)

Top network posts

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
View all tags →

Top posts (11) All Questions Answers | Votes Newest

3 Approximation Algorithm for Independet Set Problem: Any Explanation Please? Feb 16 '16
3 How to show that a problem is easy? Jan 25 '16
3 How do I select a subset such that the sum and the product are greater than some value? Feb 19 '16
2 How to match two sets of points based on the closeset distance? Jun 16 '16
2 Is the NP-hardness Proof with One Way Implication Correct and Why? Feb 22 '16
1 Is it correct to say that an algorithm ALG is an O(1)-approximation algorithm? Mar 30 '16
1 How do I select a subset such that the sum and the product are greater than some value? Feb 18 '16
1 Can I change the input of my reductionduring the proof? Feb 18 '16
1 Are these three subset sum problems hard? How to solve them? Jan 23 '16
0 Does a problem stay NP-hard when an additional constraint is added to it? Feb 27 '16
View all questions and answers →

Badges (15)

Gold

—

Silver

2

Rarest

Bronze

13

Rarest

View all badges →