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.
Bilò, D., Guala', L., Proietti, G. (2006). Designing a Truthful Mechanism for a Spanning Arborescence Bicriteria Problem. In 3rd Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2006. Springer [10.1007/11922377_3].
Designing a Truthful Mechanism for a Spanning Arborescence Bicriteria Problem
GUALA', LUCIANO;
2006-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.