A quasi-PTAS for profit-maximizing pricing on line graphs

K.M. Elbassioni, R.A. Sitters, Y. Zhang

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

25 Citations (Scopus)
101 Downloads (Pure)


We consider the problem of pricing items so as to maximize the profit made from selling these items. An instance is given by a set E of n items and a set of m clients, where each client is specified by one subset of E (the bundle of items he/she wants to buy), and a budget (valuation), which is the maximum price he is willing to pay for that subset. We restrict our attention to the model where the subsets can be arranged such that they form intervals of a line graph. Assuming an unlimited supply of any item, this problem is known as the highway problem and so far only an O(logn)-approximation algorithm is known. We show that a PTAS is likely to exist by presenting a quasi-polynomial time approximation scheme. We also combine our ideas with a recently developed quasi-PTAS for the unsplittable flow problem on line graphs to extend this approximation scheme to the limited supply version of the pricing problem.
Original languageEnglish
Title of host publicationProceedings of the 15th Annual European Symposium on Algorithms (ESA 2007) 8-10 October 2007, Eilat, Israel
EditorsL. Arge, M. Hoffmann, E. Welzl
Place of PublicationBerlin, Germany
ISBN (Print)978-3-540-75519-7
Publication statusPublished - 2007
Eventconference; ESA 2007, Eilat, Israel; 2007-10-08; 2007-10-10 -
Duration: 8 Oct 200710 Oct 2007

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conferenceconference; ESA 2007, Eilat, Israel; 2007-10-08; 2007-10-10
OtherESA 2007, Eilat, Israel

Fingerprint Dive into the research topics of 'A quasi-PTAS for profit-maximizing pricing on line graphs'. Together they form a unique fingerprint.

Cite this