Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2015) | last year (2014) | two years ago (2013) | Notes URL
 Action: login to update Options: Goto entry point

 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
 URL of the conference: URL for downloading the paper: 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
Edit History (please click the blue arrow to see the details)
Attachment Section