Assume that A and B are minimization problems. Assume that A L reduces to B via

Question

Assume that A and B are minimization problems. Assume that A L reduces to B via the functions (f g Assume that = 2 and = 1 for this L- reduction. Assume that B has a polynomial-time approximation algorithm that achieves a constant ratio of S 5. Then, what can we conclude about the approximation complexity of A? A has a polynomial-time approximation algorithm that achieves a ratio less than or equal to 5 A does not have an approximation algorithm with a ratio less than 5 A has a polynomial-time approximation algorithm that achieves a ratio less than or equal to 9. A does not have a polynomial-time approximation algorithm that achieves a ratio less than or equal to 10

Explanation / Answer

Assume that A and B are minimization problems.assume that A L-reduces to B via functions (f,g).assume alpha =2,beta =1 for l-reduction.assume that B has a polynomial -time approximation algorithm that achives a constant ratio of <=5.then what we conclude the above approximation of complexity of A?
A does not have a polynomial time approximation algorithm that achives a ratio of less than or equall to 10

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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