On Profit-Maximizing Pricing for the Highway and Tollbooth Problems

Khaled Elbassioni, Rajiv Raman, Saurabh Ray +1

In the \emph{tollbooth problem}, we are given a tree $\bT=(V,E)$ with $n$ edges, and a set of $m$ customers, each of whom is interested in purchasing a path on the tree. Each custo…