  An instance of the tollbooth problem consists of an undirected network and a
collection of single-minded customers, each of which is interested in
purchasing a fixed path subject to an individual budget constraint. The
objective is to assign a per-unit price to each edge in a way that maximizes
the collective revenue obtained from all customers. The revenue generated by
any customer is equal to the overall price of the edges in her desired path,
when this cost falls within her budget; otherwise, that customer will not
purchase any edge.
  Our main result is a deterministic algorithm for the tollbooth problem on
trees whose approximation ratio is O(log m / log log m), where m denotes the
number of edges in the underlying graph. This finding improves on the currently
best performance guarantees for trees, due to Elbassioni et al. (SAGT '09), as
well as for paths (commonly known as the highway problem), due to Balcan and
Blum (EC '06). An additional interesting consequence is a computational
separation between tollbooth pricing on trees and the original prototype
problem of single-minded unlimited supply pricing, under a plausible hardness
hypothesis due to Demaine et al. (SODA '06).
