# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### On Profit-Maximizing Pricing for the Highway and Tollbooth Problems

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Elbassioni, K., Raman, R., Ray, S., & Sitters, R. (2009). On Profit-Maximizing
Pricing for the Highway and Tollbooth Problems. In *Algorithmic Game Theory* (pp. 275-286).
Berlin: Springer. doi:10.1007/978-3-642-04645-2_25.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-1894-E

##### Abstract

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 customer has a fixed budget, and the objective is to
price the edges of $\bT$ such that the total revenue made by selling the paths
to the customers that can afford them is maximized. An important special case
of this problem, known as the \emph{highway problem}, is when $\bT$ is
restricted to be a line.
For the tollbooth problem, we present a randomized $O(\log n)$-approximation,
improving on the current best $O(\log m)$-approximation, since $n\leq 3m$ can
be assumed. We also study a special case of the tollbooth problem, when all the
paths that customers are interested in purchasing go towards a fixed root of
$\bT$. In this case, we present an algorithm that returns a
$(1-\epsilon)$-approximation, for any $\epsilon > 0$, and runs in
quasi-polynomial time. On the other hand, we rule out the existence of an FPTAS
by showing that even for the line case, the problem is strongly NP-hard.