English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

##### MPS-Authors
/persons/resource/persons44374

Elbassioni,  Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45251

Raman,  Rajiv
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45269

Ray,  Saurabh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45495

Sitters,  Rene
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### 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.