English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs

Elbassioni, K., Sitters, R., & Zhang, Y. (2007). A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs. In L. Arge, M. Hoffmann, & E. Welzl (Eds.), Algorithms - ESA 2007: 15th Annual European Symposium (pp. 451-462). Berlin, Germany: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1E25-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-AB98-3
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Elbassioni, Khaled1, Author           
Sitters, Rene1, Author           
Zhang, Yan2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2008-03-052007
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 356644
DOI: 10.1007/978-3-540-75520-3_41
Other: Local-ID: C12573CC004A8E26-D5F101BFCEF6665BC12573D70035BBB9-Elbassioni2007d
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Eilat, Israel
Start-/End Date: 2007-10-08 - 2007-10-10

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms - ESA 2007 : 15th Annual European Symposium
Source Genre: Proceedings
 Creator(s):
Arge, Lars, Editor
Hoffmann, Michael, Editor
Welzl, Emo, Editor
Affiliations:
-
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 451 - 462 Identifier: ISBN: 3-540-75519-5

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 4698 Sequence Number: - Start / End Page: - Identifier: -