Computer Science
Profile Activity
Meta user
Network profile
328
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 5 years
  • 24 profile views
  • Last seen Jan 17 '17 at 21:46

Communities (15)

Top network posts

Top tags (0)

This user has not participated in any 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 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 →