𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Decentralized pricing in minimum cost spanning trees

✍ Scribed by Jens Leth Hougaard; Hervé Moulin; Lars Peter Østerdal

Publisher
Springer
Year
2009
Tongue
English
Weight
189 KB
Volume
44
Category
Article
ISSN
0938-2259

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Improving Minimum Cost Spanning Trees by
Improving Minimum Cost Spanning Trees by Upgrading Nodes
✍ S.O Krumke; M.V Marathe; H Noltemeier; R Ravi; S.S Ravi; R Sundaram; H.-C Wirth 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 222 KB

Ž 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