Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:




Library Locked Library locked




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



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
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)
[Library]
Created
02/21/2009 04:34:19 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
0901.1140v2.pdf