An approximation algorithm for Stackelberg network pricing
An approximation algorithm for Stackelberg network pricing
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 ā¦