Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2013) | last year (2012) | two years ago (2011) | Notes URL

Action:

login to update
Options:








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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Attachment SectionAttachment Section