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


Show entries of:

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

Action:

login to update

Options:









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
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 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
02/26/2007 11:06:30 PM
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

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
htp.ps