Pricing on Paths: A PTAS for the Highway Problem
From MaRDI portal
Publication:2796210
DOI10.1137/140998846zbMath1336.68294OpenAlexW2292671995MaRDI QIDQ2796210
Thomas Rothvoß, Fabrizio Grandoni
Publication date: 23 March 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/140998846
approximation algorithmstollbooth problempricing problemshighway problemmaximum-feasibility subsystem problem
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Transportation, logistics and supply chain management (90B06) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for the unsplittable flow problem
- On the hardness of approximating max-satisfy
- A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees
- A quasi-PTAS for unsplittable flow on line graphs
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply
- A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
- Multicommodity demand flow in a tree and packing integer programs
- Single-minded unlimited supply pricing on sparse instances
- A Sublogarithmic Approximation for Highway and Tollbooth Pricing
- Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
- On Profit-Maximizing Pricing for the Highway and Tollbooth Problems
- Approximations of Weighted Independent Set and Hereditary Subset Problems
- Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path
- New Approximation Schemes for Unsplittable Flow on a Path
- A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
- Algorithms and Data Structures
- A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
- A logarithmic approximation for unsplittable flow on line graphs
- A unified approach to approximating resource allocation and scheduling
This page was built for publication: Pricing on Paths: A PTAS for the Highway Problem
