Groupe d’études et de recherche en analyse des décisions


Design and Analysis of an Approximation Algorithm for Stackelberg Network Pricing

, et

We consider the problem of maximizing the revenue raised from tolls set on the arcs of a transportation network, under the constraint that users are assigned to toll-compatible shortest paths. We first prove that this problem is strongly NP-hard. We then provide a polynomial time algorithm with a worst-case precision guarantee of (1/2)log mT+1, where mT denotes the number of toll arcs. Finally we show that the approximation is tight with respect to a natural relaxation by constructing a family of instances for which the relaxation gap is reached.

, 23 pages

Ce cahier a été révisé en mars 2003