Computer Science
1-approximation
  • Member for 5 years, 8 months
Profile Activity
Stats
338
reputation
3k
reached
2
answers
9
questions
About

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.

Communities (15)

Top network posts

This user doesn’t have any gold badges yet.
2
silver badges
13
bronze badges
View all badges

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 How to match two sets of points based on the closeset distance? Jun 16 '16
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 Is it correct to say that an algorithm ALG is an O(1)-approximation algorithm? Mar 30 '16
2 Is the NP-hardness Proof with One Way Implication Correct and Why? Feb 22 '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 →

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.