3 ms·
Unless it is an "impossibility of approximation" theorem.
by thomasahle 9y ago
Unless it is an "impossibility of approximation" theorem.
- fmap 9y agoEven that is frequently misleading. Take the problem of finding a maximum independent set. You can show that if you manage to approximate this problem within any constant factor then P = NP. On the other hand, finding large independent sets is a common subproblem in several graph reduction algorithms and simple heuristics often work very well on the graphs that occur in practice.