On the complexity of the highway problem

DOI10.1016/j.tcs.2012.07.028zbMath1253.68172MaRDI QIDQ690481

Saurabh Ray, Rajiv Raman, Khaled M. Elbassioni, R. 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

zbMATH Keywords

complexity; approximation algorithms; NP-hardness; pricing; interval graphs; hardness of approximation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C27: Combinatorial optimization

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A QPTAS for -Envy-Free Profit-Maximizing Pricing on Line Graphs
• A Nonparametric Approach to Multiproduct Pricing
• How to Sell a Graph: Guidelines for Graph Retailers
• A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
• On the power of unique 2-prover 1-round games
• Combination can be hard
• Knapsack auctions
• Single-minded unlimited supply pricing on sparse instances
• A Sublogarithmic Approximation for Highway and Tollbooth Pricing
• On Hardness of Pricing Items for Single-Minded Bidders
• On Profit-Maximizing Pricing for the Highway and Tollbooth Problems
• Algorithms and Data Structures