MPI-INF D1 Publications: Unpublished/Draft

Unpublished, Draft, To Appear
@UnPublished
Unveröffentlicht, Entwurf

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Goto entry point

Author, Editor

Author(s):

Elbassioni, Khaled M.
Sitters, Rene
Zhang, Yan

dblp
dblp
dblp

Not MPG Author(s):

Sitters, Rene
Zhang, Yan

BibTeX citekey*:

Elbassioni2007b

Title, Booktitle

Title*:

A Quasi-PTAS for Envy-free Pricing on Line Graphs

Vol, No, pp., Year

Month:	January	Year:	2007
Language:	English	Pages:

Abstract, Links, ©

Note:
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 wants to buy), and a budget, which is the maximum price he wants to pay for the subset. We restrict to the model where the subsets can be arranged such that they form intervals of a line graph. We give a quasi-polynomial time approximation scheme for the capacitated and uncapacitated problem. In the latter problem, also known as the highway problem, there is an infinite supply of any item. Hence, we assume that any client that can afford its bundle will buy it. In the capacitated problem there is only a limited supply of any item. Hence, we have to set prices as well to find a subset of the clients such that the supply constraints are satisfied. This problem is closely related to the unsplittable flow problem on line graphs for which a quasi-PTAS was developed only recently.
Categories / Keywords:
HyperLinks / References / URLs:
Personal Comments:
File Upload:

Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@UNPUBLISHED{Elbassioni2007b,
AUTHOR = {Elbassioni, Khaled M. and Sitters, Rene and Zhang, Yan},
TITLE = {A Quasi-PTAS for Envy-free Pricing on Line Graphs},
YEAR = {2007},
MONTH = {January},
}

Entry last modified by Christine Kiesel, 02/28/2008

Edit History (please click the blue arrow to see the details)

	Editor(s) Khaled Elbassioni	Created 02/26/2007 23:06:30
Revisions 2. 1. 0.	Editor(s) Christine Kiesel Khaled Elbassioni Khaled Elbassioni	Edit Dates 02.05.2007 15:29:12 03/02/2007 05:33:40 PM 02/26/2007 11:06:30 PM

Attachment Section

htp.ps

htp.ps