On profit-maximizing pricing for the highway and tollbooth problems

Khaled Elbassioni, Rajiv Raman, Saurabh Ray, René Sitters

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

23 Scopus citations


In the tollbooth problem on trees, we are given a tree T = (V,E) with n edges, and a set of m customers, each of whom is interested in purchasing a path on the graph. Each customer has a fixed budget, and the objective is to price the edges of T 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 highway problem, is when T is restricted to be a line. For the tollbooth problem, we present an O(logn)-approximation, improving on the current best O(logm)-approximation. 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 T. In this case, we present an algorithm that returns a (1-ε)-approximation, for any ε > 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. Finally, we show that in the discount model, when we allow some items to be priced below zero to improve the overall profit, the problem becomes even APX-hard.

Original languageBritish English
Title of host publicationAlgorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings
Number of pages12
StatePublished - 2009
Event2nd International Symposium on Algorithmic Game Theory, SAGT 2009 - Paphos, Cyprus
Duration: 18 Oct 200920 Oct 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5814 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference2nd International Symposium on Algorithmic Game Theory, SAGT 2009


Dive into the research topics of 'On profit-maximizing pricing for the highway and tollbooth problems'. Together they form a unique fingerprint.

Cite this