A sublogarithmic approximation for highway and tollbooth pricing

DOI10.1007/978-3-642-14165-2_49MaRDI QIDQ3587409zbMATH OpenOpenAlexFDO

Authors Iftah Gamzu, Danny Segev

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1002.2084

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

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, 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).

Recommendations

• A sublogarithmic approximation for tollbooth pricing on trees
• On profit-maximizing pricing for the highway and tollbooth problems
• On the complexity of the highway pricing problem
• Pricing on paths: a PTAS for the highway problem
• Pricing on paths: a PTAS for the highway problem

Cited in

(14)

• On the complexity of the highway problem
• Improved approximation for orienting mixed graphs
• Graph pricing with limited supply
• Packing cars into narrow roads: PTASs for limited supply highway
• On the hardness of pricing loss-leaders
• On the complexity of the highway pricing problem
• Highway toll pricing
• On profit-maximizing pricing for the highway and tollbooth problems
• Pricing on paths: a PTAS for the highway problem
• An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph
• Pricing on paths: a PTAS for the highway problem
• A path-decomposition theorem with applications to pricing and covering on trees
• Improved hardness results for profit maximization pricing problems with unlimited supply
• A sublogarithmic approximation for tollbooth pricing on trees

This page was built for publication: A sublogarithmic approximation for highway and tollbooth pricing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587409)