A Sublogarithmic Approximation for Highway and Tollbooth Pricing
From MaRDI portal
Publication:3587409
DOI10.1007/978-3-642-14165-2_49zbMath1288.68265arXiv1002.2084MaRDI QIDQ3587409
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
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
68W25: Approximation algorithms
Related Items
Unnamed Item, Unnamed Item, Improved approximation for orienting mixed graphs, An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph, On the complexity of the highway problem, Graph pricing with limited supply, Pricing on Paths: A PTAS for the Highway Problem