MPI-INF D1 Publications: Proceedings Article: A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

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:


(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)

	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

Attachment Section