MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Elbassioni, Khaled
Sitters, Rene
Zhang, Yan
dblp
dblp
dblp
Not MPG Author(s):
Sitters, Rene
Zhang, Yan
Editor(s):
Arge, Lars
Hoffmann, Michael
Welzl, Emo
dblp
dblp
dblp
Not MPII Editor(s):
Arge, Lars
Hoffmann, Michael
Welzl, Emo
BibTeX cite key*:
Elbassioni2007d
Title, Booktitle
Title*:
A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
Booktitle*:
Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Eilat, Israel
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
8 October 2007
Event End Date:
10 October 2007
Publisher
Name*:
Springer
URL:
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4698
Number:
Month:
October
Pages:
451-462
Year*:
2007
VG Wort Pages:
12
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
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 \emph{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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Elbassioni2007d,
AUTHOR = {Elbassioni, Khaled and Sitters, Rene and Zhang, Yan},
EDITOR = {Arge, Lars and Hoffmann, Michael and Welzl, Emo},
TITLE = {A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs},
BOOKTITLE = {Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings},
PUBLISHER = {Springer},
YEAR = {2007},
VOLUME = {4698},
PAGES = {451--462},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Eilat, Israel},
MONTH = {October},
}


Entry last modified by Khaled Elbassioni, 02/28/2008
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Khaled Elbassioni
Created
01/21/2008 10:46:54 AM
Revisions
3.
2.
1.
0.
Editor(s)
Khaled Elbassioni
Khaled Elbassioni
Khaled Elbassioni
Khaled Elbassioni
Edit Dates
01/21/2008 11:17:44 AM
01/21/2008 10:54:24 AM
01/21/2008 10:53:57 AM
01/21/2008 10:46:54 AM