✦ LIBER ✦

Hardness results for multicast cost sharing

✍ Scribed by Joan Feigenbaum; Arvind Krishnamurthy; Rahul Sami; Scott Shenker

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 308 KB
Volume: 304
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(03)00085-9

No coin nor oath required. For personal study only.

✦ Synopsis

We continue the study of multicast cost sharing from the viewpoints of both computational complexity and economic mechanism design. We provide fundamental lower bounds on the network complexity of group-strategyproof, budget-balanced mechanisms. We also extend a classical impossibility result in game theory to show that no strategyproof mechanism can be both approximately e cient and approximately budget-balanced. Our results show that one important and natural case of multicast cost sharing is an example of a canonical hard problem in distributed, algorithmic mechanism design; in this sense, they represent progress toward the development of a complexity theory of Internet computation.

📜 SIMILAR VOLUMES

Sharing the Cost of Multicast Transmissi

Sharing the Cost of Multicast Transmissions

✍ Joan Feigenbaum; Christos H. Papadimitriou; Scott Shenker 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 207 KB

We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most appropriate in this context. We prove that the former has a natural algorithm that uses only two messages per link o

An efficient implementation of tree-base

An efficient implementation of tree-based multicast routing for distributed shared-memory multiprocessors

✍ M.P. Malumbres; José Duato 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 398 KB

This paper presents an ecient routing and ¯ow control mechanism to implement multidestination message passing in wormhole networks. The mechanism is a variation of tree-based multicast with pruning to recover from deadlocks and it is well suited for distributed shared-memory multiprocessors (DSMs) w

A cost-sharing method for an economic lo

A cost-sharing method for an economic lot-sizing game

✍ Dachuan Xu; Ruichun Yang 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 723 KB

We present a cost-sharing method that is competitive, cross-monotonic and approximate cost recovering for an economic lot-sizing game under a weak triangle inequality assumption, along with numerical results showing the effectiveness of the proposed method.

Hardness results for weak bisimilarity o

Hardness results for weak bisimilarity of simple process algebras

✍ Jitka StříAbrná 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 709 KB

Further results on weighted sharing of v

Further results on weighted sharing of values for meromorphic functions

✍ Xiao-Min Li; Hong-Xun Yi 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 735 KB

A new heuristic algorithm for finding mi

A new heuristic algorithm for finding minimum-cost multicast trees with bounded path delay

✍ Anna Hać; Kelei Zhou 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB

## This article presents a new heuristic algorithm called DDBMA (Dynamic Delay Bounded Multicast Algorithm) to construct a minimum-cost multicast tree. The heuristic depends on (1) bounded delay along paths from source nodes to each destination node; (2) minimum cost of the multicast tree; (3) dyn