Pricing on paths: a PTAS for the highway problem

zbMATH Open1377.90100MaRDI QIDQ5365072FDOQ5365072

Authors: Fabrizio Grandoni, Thomas Rothvoß 

Publication date: 29 September 2017

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

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

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)

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
• On the hardness of pricing loss-leaders
• Packing cars into narrow roads: PTASs for limited supply highway
• 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)