PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
Approach Taken:
Determining the optimal solution is NP-hard so one has to resort to heuristics to solve the problem. The reduction showing NP-hardness is not obvious; [1] shows weak NP-hardness and [2] improves this to strong NP-hardness. There is a very simple poly-time algorithm that is guaranteed to find at least a 1/log (N * M) fraction of the optimum cost [3]. It can be described in very simple terms: for each number T of the form B _ i/|t _ i - s _ i| (budget divided by length), set the prices of all edges to T. Use the value T that maximizes the total revenue of all clients who can afford paying T times the number of tolls they cross. This is the starting point for quite a few heuristics that can be tried. Some of the best solutions employed very interesting tools including dynamic programming approaches and using linear programming techniques.
In theory, for every constant eps > 0 one can get at least a (1-eps) times the optimum profit in time O(n^(c/eps)) for some constant c [4]. The algorithm isn’t very practical in practice, but it does show that in theory we can get within any given constant factor of the optimum in polynomial time.
While the condition that the prices be integers in output for the problem might seem like a restriction, one can actually show that if all budgets are integer then there is an assignment of non-negative integer tolls to the tollbooths that achieves the maximum possible profit (so we don’t need rational numbers).
[1] Single-Minded Unlimited Supply Pricing on Sparse Instances, P. Briest and P. Krysta
[2] On Profit-Maximizing Pricing for the Highway and Tollbooth Problems, K. Elbassioni, R. Ramen, S. Ray, and R. Sitters.
[3] On Profit-Maximizing Envy-Free Pricing, V. Guruswami, J. Hartline, A. Karlin, D. Kempe, C. Kenyon, and F. McSherry.
[4] Prizing on Paths: A PTAS for the Highway Problem, F. Grandoni and T. Rothvoss