A Sublogarithmic Approximation for Tollbooth Pricing on Trees

Iftah Gamzu () and Danny Segev ()
Additional contact information
Iftah Gamzu: Yahoo! Research, Haifa, Israel
Danny Segev: Department of Statistics, University of Haifa, Haifa 31905, Israel

Mathematics of Operations Research, 2017, vol. 42, issue 2, 377-388

Abstract: 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, and up until recently, also on the best ratio for paths (commonly known as the highway problem). 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.

Keywords: pricing; approximation algorithms; tollbooth problem; highway problem; trees; balanced decompositions; segment guessing; randomization (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0803 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:2:p:377-388

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().