Journal
NETWORKS
Volume 46, Issue 1, Pages 57-67Publisher
WILEY-BLACKWELL
DOI: 10.1002/net.20074
Keywords
network pricing; approximation algorithms; Stackelberg games; combinatorial optimization; NP-hard problems
Ask authors/readers for more resources
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(2)m(T) + 1, where m(T) 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. (c) 2005 Wiley Periodicals, Inc.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available