TY - GEN

T1 - On profit-maximizing pricing for the highway and tollbooth problems

AU - Elbassioni, Khaled

AU - Raman, Rajiv

AU - Ray, Saurabh

AU - Sitters, René

PY - 2009

Y1 - 2009

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

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

UR - http://www.scopus.com/inward/record.url?scp=71549145635&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=71549145635&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-04645-2_25

DO - 10.1007/978-3-642-04645-2_25

M3 - Conference contribution

AN - SCOPUS:71549145635

SN - 3642046444

SN - 9783642046445

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 275

EP - 286

BT - Algorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings

T2 - 2nd International Symposium on Algorithmic Game Theory, SAGT 2009

Y2 - 18 October 2009 through 20 October 2009

ER -