Group: uw.cs.cs341 · Group Profile · Search for Exam 2 in uw.cs.cs341
Author: Thomas Dimson
Date: Jul 31, 2008 18:43
Chenen Liang wrote: True or False: No NP-hard problem has a polynomial-time algorithm with an approximation ratio ≤ 2. Justify your answer. what is approximation ratio? Wikipedia seems to indicate it is something that is hard to understand (at least without seeing it in lecture), I'm sure we didn't cover it. True or False: All decision problems can be solved in ...
|