Computer Science – Data Structures and Algorithms
Scientific paper
2010-02-10
Computer Science
Data Structures and Algorithms
14 pages, 3 figure
Scientific paper
An instance of the tollbooth problem consists of an undirected network and a collection of single-minded customers, each of which is interested in purchasing a fixed path subject to an individual budget constraint. The objective is to assign a per-unit price to each edge in a way that maximizes the collective revenue obtained from all customers. The revenue generated by any customer is equal to the overall price of the edges in her desired path, when this cost falls within her budget; otherwise, that customer will not purchase any edge. Our main result is a deterministic algorithm for the tollbooth problem on trees whose approximation ratio is O(log m / log log m), where m denotes the number of edges in the underlying graph. This finding improves on the currently best performance guarantees for trees, due to Elbassioni et al. (SAGT '09), as well as for paths (commonly known as the highway problem), due to Balcan and Blum (EC '06). An additional interesting consequence is a computational separation between tollbooth pricing on trees and the original prototype problem of single-minded unlimited supply pricing, under a plausible hardness hypothesis due to Demaine et al. (SODA '06).
Gamzu Iftah
Segev Danny
No associations
LandOfFree
A Sublogarithmic Approximation for Highway and Tollbooth Pricing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Sublogarithmic Approximation for Highway and Tollbooth Pricing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Sublogarithmic Approximation for Highway and Tollbooth Pricing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-238886