A Truthful (2-2/k)-Approximation 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 non-cooperative 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 k is the number of terminal nodes, and α(.,.) is the classic inverse of the Ackermann's function. This compares favorably with the previous known O(kn(m + n log n)) time and 2-approximate truthful mechanism for solving the problem.