Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1E25-B Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-AB98-3
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Elbassioni, Khaled1, Autor           
Sitters, Rene1, Autor           
Zhang, Yan2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2008-03-052007
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 356644
DOI: 10.1007/978-3-540-75520-3_41
Anderer: Local-ID: C12573CC004A8E26-D5F101BFCEF6665BC12573D70035BBB9-Elbassioni2007d
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Eilat, Israel
Start-/Enddatum: 2007-10-08 - 2007-10-10

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Algorithms - ESA 2007 : 15th Annual European Symposium
Genre der Quelle: Konferenzband
 Urheber:
Arge, Lars, Herausgeber
Hoffmann, Michael, Herausgeber
Welzl, Emo, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 451 - 462 Identifikator: ISBN: 3-540-75519-5

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 4698 Artikelnummer: - Start- / Endseite: - Identifikator: -