On the complexity of the highway problem
DOI10.1016/J.TCS.2012.07.028zbMATH Open1253.68172OpenAlexW2133213475MaRDI QIDQ690481FDOQ690481
Saurabh Ray, Rajiv Raman, Khaled Elbassioni, René A. Sitters
Publication date: 27 November 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.07.028
Recommendations
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- On profit-maximizing envy-free pricing
- Single-minded unlimited supply pricing on sparse instances
- A Sublogarithmic Approximation for Highway and Tollbooth Pricing
- On profit-maximizing pricing for the highway and tollbooth problems
- Title not available (Why is that?)
- Algorithms and Data Structures
- On the power of unique 2-prover 1-round games
- Knapsack auctions
- A Nonparametric Approach to Multiproduct Pricing
- Title not available (Why is that?)
- A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
- On Hardness of Pricing Items for Single-Minded Bidders
- Title not available (Why is that?)
- How to Sell a Graph: Guidelines for Graph Retailers
- Combination can be hard
- A QPTAS for -Envy-Free Profit-Maximizing Pricing on Line Graphs
- Title not available (Why is that?)
Cited In (5)
This page was built for publication: On the complexity of the highway problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q690481)
