Algorithm. Check one answer per question: Yes, no, or don\'t know. Check whichev

Question

Algorithm.

Check one answer per question: Yes, no, or don't know.

Check whichever applied to the traveling salesman problem: a. NP-complete Yes No Don't know b. Solvable exactly in pt (polynomial time) Yes No Don't know c. Approximable in pt within factor 2.9999 Yes No Don't know d. Approximable in pt within factor 1.9999 Yes No Don't know e. Approximable in pt within factor 1.5999 Yes No Don't know Check whichever applied to the vertex cover problem (assuming P notequalto NP) a. NP-complete Yes No Don't know b. Solvable exactly in pt (polynomial time) Yes No Don't know c. Approximable in pt within factor 2.9999 Yes No Don't know d. Approximable in pt within factor 1.9999 Yes No Don't know e. Approximable in pt within factor 1.0001 Yes No Don't know Check whichever applied to the clique problem in graphs: a. NP-complete Yes No Don't know b. Solvable exactly in pt (polynomial time) Yes No Don't know c. Approximable in pt within factor 2.9999 Yes No Don't know d. Approximable in pt within factor 1.999

Explanation / Answer

1)
a. Yes
b. No
c. No
d. No
e. No

2)
a. Yes
b. No
c. No
d. No
e. No

3)
a. Yes
b. No
c. No
d. No
e. No

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.