TRUE, FALSE or UNKNOWN - beef up your grade Each question is 4 points. If you wa
ID: 3739786 • Letter: T
Question
TRUE, FALSE or UNKNOWN - beef up your grade Each question is 4 points. If you want to explain your reasoning to get partial credit feel free to do so 1. The approximation ratio for Center selection problem obtained by TRUE FALE greedy algorithm can be improved with LP+rounding method. FALSE UNK town 2. Relaxation to linear programming with rounding for weighted vertex cover gives better ratio than pricing method TRUE FALSE UKNOW 3. Assuming P NP, set cover problem can be approximatedTRUE FALSE within the ratio of 2 TRUE FALSE UNKNOWN TRUE FALSE UNKNOW If a problem has a certificate of size log n for an instance of size n then it is in P 5.Explanation / Answer
1.
True.
The appoximation ratio for center selection problems obtained by greedy algorithm can be implemented by LP+ routing method.
2.
True.
Relaxationship with linear programming with routing for weighted vertex cover gives better ratio than pricing method.
3.
False
Assuming P?NP set cover problem can be non-existence of efficient algorithms with certain approximation ratios.
4.
False.
Since NP is a subset or equal to the set of complements of the problems.
NP?coNP
5.
True
If a problem has a certificate of size log n for an instance of size n then it is in P.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.