Pricing on Paths: A PTAS for the Highway Problem

In the highway problem, we are given an $n$-edge path graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the associated path, when it does not exceed the budget of the driver, and zero otherwise. The goal is to choose weights so as to maximize the profit. A lot of research has been devoted to this apparently simple problem. The highway problem was shown to be strongly $\mathbf{NP}$-hard only recently [K. M. Elbassioni et al., in Proceedings of the International Symposium on Algorithmic Game Theory (SAGT), 2009, pp. 275--286]. The best-known approximation is $O(\log n/\log\log n)$ [I. Gamzu and D. Segev, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2010, pp. 582--593], which improves on the previous best $O(\log n)$ approximation [M.-F. Balcan and A. Blum, in Proceedings of the ACM Conference on Electronic Commerce,...