Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Elbassioni, Khaled Raman, Rajiv Ray, Saurabh Sitters, Rene dblp dblp dblp dblp Not MPG Author(s): Sitters, Rene
 Editor(s): Mavronicolas, Marios Papadopoulou, Vicky G. dblp dblp Not MPII Editor(s): Mavronicolas, Marios Papadopoulou, Vicky G.
 BibTeX cite key*: Raman2009

 Title, Booktitle
 Title*: On Profit-Maximizing Pricing for the Highway and Tollbooth Problems 0901.1140v2.pdf (217.17 KB) Booktitle*: Algorithmic Game Theory : Second International Symposium, SAGT 2009

 Event, URLs
 URL of the conference: URL for downloading the paper: http://arxiv.org/abs/0901.1140v3 Event Address*: Paphos, Cyprus Language: English Event Date* (no longer used): Organization: Event Start Date: 18 October 2009 Event End Date: 20 October 2009

 Publisher
 Name*: Springer URL: Address*: Berlin, Germany Type:

 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 5814 Number: Month: Pages: 275-286 Year*: 2009 VG Wort Pages: ISBN/ISSN: 978-3-642-04644-5 Sequence Number: DOI: 10.1007/978-3-642-04645-2_25

 (LaTeX) Abstract: In the \emph{tollbooth problem}, we are given a tree $\bT=(V,E)$ with $n$ edges, and a set of $m$ customers, each of whom is interested in purchasing a path on the tree. Each customer has a fixed budget, and the objective is to price the edges of $\bT$ such that the total revenue made by selling the paths to the customers that can afford them is maximized. An important special case of this problem, known as the \emph{highway problem}, is when $\bT$ is restricted to be a line. For the tollbooth problem, we present a randomized $O(\log n)$-approximation, improving on the current best $O(\log m)$-approximation, since $n\leq 3m$ can be assumed. We also study a special case of the tollbooth problem, when all the paths that customers are interested in purchasing go towards a fixed root of $\bT$. In this case, we present an algorithm that returns a $(1-\epsilon)$-approximation, for any $\epsilon > 0$, and runs in quasi-polynomial time. On the other hand, we rule out the existence of an FPTAS by showing that even for the line case, the problem is strongly NP-hard. Keywords: Data Structures and Algorithms, Computer Science and Game Theory HyperLinks / References / URLs: http://arxiv.org/abs/0901.1140 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:

@INPROCEEDINGS{Raman2009,
AUTHOR = {Elbassioni, Khaled and Raman, Rajiv and Ray, Saurabh and Sitters, Rene},
EDITOR = {Mavronicolas, Marios and Papadopoulou, Vicky G.},
TITLE = {On Profit-Maximizing Pricing for the Highway and Tollbooth Problems},
BOOKTITLE = {Algorithmic Game Theory : Second International Symposium, SAGT 2009},
JOURNAL = {ArXiv.org},
PUBLISHER = {Springer},
YEAR = {2009},
VOLUME = {5814},
PAGES = {275--286},
SERIES = {Lecture Notes in Computer Science},