MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
Downloading URL:
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
Note, Abstract, ©
(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},
 ADDRESS = {Paphos, Cyprus},
 ISBN = {978-3-642-04644-5},
 DOI = {10.1007/978-3-642-04645-2_25},
}

Entry last modified by Anja Becker, 03/08/2010
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)
[Library]		Created
02/21/2009 16:34:19
Revisions
5.
4.
3.
2.
1.		Editor(s)
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Anja Becker		Edit Dates
08.03.2010 12:29:11
04.03.2010 16:48:01
04.03.2010 16:47:16
04.03.2010 16:46:15
03/27/2009 12:18:21 PM

File Attachment Icon
0901.1140v2.pdf