On the complexity of the highway problem

DOI10.1016/J.TCS.2012.07.028MaRDI QIDQ690481zbMATH OpenOpenAlexFDO

Authors Rajiv Raman, Saurabh Ray, 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

zbMATH Keywords

complexityapproximation algorithmsinterval graphspricingNP-hardnesshardness of approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the complexity of the highway pricing problem
• Pricing on paths: a PTAS for the highway problem
• On profit-maximizing pricing for the highway and tollbooth problems
• Pricing on paths: a PTAS for the highway problem
• On the hardness of pricing loss-leaders

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• A Nonparametric Approach to Multiproduct Pricing
• A QPTAS for -Envy-Free Profit-Maximizing Pricing on Line Graphs
• A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
• A sublogarithmic approximation for highway and tollbooth pricing
• Algorithms and Data Structures
• Approximation algorithms and online mechanisms for item pricing
• Buying cheap is expensive: hardness of non-parametric multi-product pricing
• Combination can be hard
• How to Sell a Graph: Guidelines for Graph Retailers
• Knapsack auctions
• On Hardness of Pricing Items for Single-Minded Bidders
• On profit-maximizing envy-free pricing
• On profit-maximizing pricing for the highway and tollbooth problems
• On the hardness of pricing loss-leaders
• On the power of unique 2-prover 1-round games
• Pricing on paths: a PTAS for the highway problem
• Single-minded unlimited supply pricing on sparse instances

Cited in

(8)

• The 1-median and 1-highway problem
• On the complexity of the highway pricing problem
• On the hardness of pricing loss-leaders
• Packing cars into narrow roads: PTASs for limited supply highway
• The chilean highway problem
• On profit-maximizing pricing for the highway and tollbooth problems
• Pricing on paths: a PTAS for the highway problem
• On complexity classes of envy-free pricing problems: a short survey

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)