Advertisement
Published in:
2006 | OriginalPaper | Chapter
Designing a Truthful Mechanism for a Spanning Arborescence Bicriteria Problem
Authors : Davide Bilò, Luciano Gualà, Guido Proietti
Published in: Combinatorial and Algorithmic Aspects of Networking
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.