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 contribution

Abstract

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 languageEnglish (US)
Title of host publicationAlgorithmic Game Theory - Second International Symposium, SAGT 2009, Proceedings
Pages275-286
Number of pages12
DOIs
StatePublished - 2009
Event2nd International Symposium on Algorithmic Game Theory, SAGT 2009 - Paphos, Cyprus
Duration: Oct 18 2009Oct 20 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

Other

Other2nd International Symposium on Algorithmic Game Theory, SAGT 2009
CountryCyprus
CityPaphos
Period10/18/0910/20/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this