TY - GEN

T1 - Pricing tree access networks with connected backbones

AU - Goyal, Vineet

AU - Gupta, Anupam

AU - Leonardi, Stefano

AU - Ravi, R.

PY - 2007

Y1 - 2007

N2 - Consider the following network subscription pricing problem. We are given a graph G= (V, E) with a root r, and potential customers are companies headquartered at r with locations at a subset of nodes. Every customer requires a network connecting its locations to r. The network provider can build this network with a combination of backbone edges (consisting of high capacity cables) that can route any subset of the customers, and access edges that can route only a single customer's traffic. The backbone edges cost M times that of the access edges. Our goal is to devise a group-strategyproof pricing mechanism for the network provider, i.e., one in which truth-telling is the optimal strategy for the customers, even in the presence of coalitions. We give a pricing mechanism that is 2-competitive and O(1)-budget-balanced. As a means to obtaining this pricing mechanism, we present the first primaldual 8-approximation algorithm for this problem. Since the two-stage Stochastic Steiner tree problem can be reduced to the underlying network design, we get a primal-dual algorithm for the stochastic problem as well. Finally, as a byproduct of our techniques, we also provide bounds on the inefficiency of our mechanism.

AB - Consider the following network subscription pricing problem. We are given a graph G= (V, E) with a root r, and potential customers are companies headquartered at r with locations at a subset of nodes. Every customer requires a network connecting its locations to r. The network provider can build this network with a combination of backbone edges (consisting of high capacity cables) that can route any subset of the customers, and access edges that can route only a single customer's traffic. The backbone edges cost M times that of the access edges. Our goal is to devise a group-strategyproof pricing mechanism for the network provider, i.e., one in which truth-telling is the optimal strategy for the customers, even in the presence of coalitions. We give a pricing mechanism that is 2-competitive and O(1)-budget-balanced. As a means to obtaining this pricing mechanism, we present the first primaldual 8-approximation algorithm for this problem. Since the two-stage Stochastic Steiner tree problem can be reduced to the underlying network design, we get a primal-dual algorithm for the stochastic problem as well. Finally, as a byproduct of our techniques, we also provide bounds on the inefficiency of our mechanism.

UR - http://www.scopus.com/inward/record.url?scp=38049046689&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38049046689&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-75520-3_45

DO - 10.1007/978-3-540-75520-3_45

M3 - Conference contribution

AN - SCOPUS:38049046689

SN - 9783540755197

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 498

EP - 509

BT - Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings

PB - Springer Verlag

T2 - 15th Annual European Symposium on Algorithms, ESA 2007

Y2 - 8 October 2007 through 10 October 2007

ER -