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.
Designing a Truthful Mechanism for a Spanning Arborescence Bicriteria Problem / Bilò, Davide; Gualà, Luciano; Proietti, Guido. - 4235:(2006), pp. 19-30. (Intervento presentato al convegno 3rd Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN'06)) [10.1007/11922377_3].
Designing a Truthful Mechanism for a Spanning Arborescence Bicriteria Problem
BILÒ, Davide;
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.