On the complexity of the highway problem

DOI10.1016/J.TCS.2012.07.028zbMATH Open1253.68172OpenAlexW2133213475MaRDI QIDQ690481FDOQ690481

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

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

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)

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
• Pricing on paths: a PTAS for the highway problem
• Algorithms and Data Structures
• On the power of unique 2-prover 1-round games
• Knapsack auctions
• A Nonparametric Approach to Multiproduct Pricing
• Approximation algorithms and online mechanisms for item pricing
• A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
• On Hardness of Pricing Items for Single-Minded Bidders
• Buying cheap is expensive: hardness of non-parametric multi-product pricing
• How to Sell a Graph: Guidelines for Graph Retailers
• Combination can be hard
• A QPTAS for -Envy-Free Profit-Maximizing Pricing on Line Graphs
• On the hardness of pricing loss-leaders

Cited In (8)

• The chilean highway problem
• On the hardness of pricing loss-leaders
• Packing cars into narrow roads: PTASs for limited supply highway
• On the complexity of the highway pricing problem
• On profit-maximizing pricing for the highway and tollbooth problems
• Pricing on paths: a PTAS for the highway problem
• The 1-median and 1-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)