Back to Search
Start Over
Designing a Truthful Mechanism for a Spanning Arborescence Bicriteria Problem.
- Source :
- Combinatorial & Algorithmic Aspects of Networking: Third Workshop, Caan 2006, Chester, Uk, July 2, 2006. Revised Papers; 2006, p19-30, 12p
- Publication Year :
- 2006
-
Abstract
- Let a communication network be modelled by a directed graph G=(V,E) of n nodes and m edges, and assume that each edge is owned by a selfish agent, which privately holds a pair of values associated with the edge, namely its cost and its length. In this paper we analyze the problem of designing a truthful mechanism for computing a spanning arborescence of G rooted at a fixed node r ϵV having minimum cost (as computed w.r.t. the cost function) among all the spanning arborescences rooted at r which satisfy the following constraint: for each node, the distance from r (as computed w.r.t. the length function) must not exceed a fixed bound associated with the node. First, we prove that the problem is hard to approximate within better than a logarithmic factor, unless NP admits slightly superpolynomial time algorithms. Then, we provide a truthful single-minded mechanism for the problem, which guarantees an approximation factor of (1+ε)(n–1), for any ε>0. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540488224
- Database :
- Complementary Index
- Journal :
- Combinatorial & Algorithmic Aspects of Networking: Third Workshop, Caan 2006, Chester, Uk, July 2, 2006. Revised Papers
- Publication Type :
- Book
- Accession number :
- 76794062
- Full Text :
- https://doi.org/10.1007/11922377_3