A Truthful (2-2/k)-Approzimation Mechanism for the Steiner Tree Problem with k Terminals
Let a communication network be modelled by an undirected graph G=(V, E) of n nodes and m edges, and assume that each edge is owned by a selfish agent, which establishes the cost of using her edge by pursuing only her personal utility. In such a noncooperative setting, we aim at designing a truthful mechanism for the problem of finding a minimuM Steiner tree of G. Since no poly-time computable exact truthful mechanism can exist for such a probleM (unless P=NP), we provide a truthful (2-2/k)approximation mechanism which can be computed in O((n + k2)m log α(m, n)) time, where A; is the number of terminal nodes, and α(·,·) is the classic inverse of the Ackermanns function. This compares favorably with the previous known O(kn(M + n log n)) time and 2-approximate truthful mechanism for solving the problem.
Steiner Tree Problem Selfish Agents Algorithmic Mechanism Design Approzimate Truthful Mechanismsh
Luciano Guala Guido Proietti
Dipartimento di Informatics, Universita di LAquila, Italy Dipartimento di Informatics, Universita di LAquila, Italy Istituto di Analisi dei Sistemi ed Inform
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
390-400
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）