An approximation algorithm for Stackelberg network pricing

An approximation algorithm for Stackelberg network pricing

0.00 Avg rating0 Votes
Article ID: iaor20053332
Country: United States
Volume: 46
Issue: 1
Start Page Number: 57
End Page Number: 67
Publication Date: Jun 2005
Journal: Networks
Authors: , ,
Abstract:

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/2log2mT + 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.

Reviews

Required fields are marked *. Your email address will not be published.