A Sublogarithmic Approximation for Highway and Tollbooth Pricing

DOI10.1007/978-3-642-14165-2_49zbMath1288.68265arXiv1002.2084OpenAlexW1505323399MaRDI QIDQ3587409

Danny Segev, Iftah Gamzu

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)

Related Items (7)

Graph pricing with limited supply ⋮ An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph ⋮ On the complexity of the highway problem ⋮ Unnamed Item ⋮ Pricing on Paths: A PTAS for the Highway Problem ⋮ Unnamed Item ⋮ Improved approximation for orienting mixed graphs

This page was built for publication: A Sublogarithmic Approximation for Highway and Tollbooth Pricing