Pricing on paths: a PTAS for the highway problem

MaRDI QIDQ5365072zbMATH OpenFDO

Authors Fabrizio Grandoni, Thomas Rothvoß

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133089

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

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

Cited in

(12)

• On the complexity of the highway problem
• On revenue maximization with sharp multi-unit demands
• Graph pricing with limited supply
• A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
• 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
• On profit-maximizing pricing for the highway and tollbooth problems
• A sublogarithmic approximation for highway and tollbooth pricing
• Pricing on paths: a PTAS for the highway problem
• A polynomial time approximation scheme for the problem of interconnecting highways
• An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph

This page was built for publication: Pricing on paths: a PTAS for the highway problem

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