TY - GEN
T1 - A quasi-PTAS for profit-maximizing pricing on line graphs
AU - Elbassioni, Khaled
AU - Sitters, René
AU - Yan, Zhang
PY - 2007
Y1 - 2007
N2 - 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(log n)-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.
AB - 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(log n)-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.
UR - http://www.scopus.com/inward/record.url?scp=38049086781&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38049086781&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:38049086781
SN - 9783540755197
VL - 4698 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 451
EP - 462
BT - Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings
T2 - 15th Annual European Symposium on Algorithms, ESA 2007
Y2 - 8 October 2007 through 10 October 2007
ER -
