Improving Minimum Cost Spanning Trees by Upgrading Nodes

✍ Scribed by S.O Krumke; M.V Marathe; H Noltemeier; R Ravi; S.S Ravi; R Sundaram; H.-C Wirth

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 222 KB
• Volume: 33
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1999.1021

✦ Synopsis

Ž O O Žlog log n. . 2. In contrast, we show that, unless NP : DTIME n , there can be no polynomial time approximation algorithm for the problem that produces a solution with upgrading cost at most ␣ln n times the optimal upgrading cost Ž . even if the budget can be violated by a factor f n , for any polynomial time Ž . Ž .

k computable function f n . This result continues to hold, with f n s n being any polynomial, even when the difference between the maximum and minimum edge weights is bounded by a polynomial in n.

3. Finally, we show that using a sample binary search over the set of admissible values, the dual problem can be solved with an appropriate performance guarantee.