On Hardness of Pricing Items for Single-Minded Bidders

DOI10.1007/978-3-642-03685-9_16MaRDI QIDQ3638879zbMATH OpenOpenAlexFDO

Authors Rohit Khandekar, Konstantin Makarychev, Maxim Sviridenko, Tracy Kimbrel

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03685-9_16

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Auctions, bargaining, bidding and selling, and other market models (91B26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Microeconomic theory (price theory and economic markets) (91B24)

Recommendations

• Approximation algorithms and online mechanisms for item pricing
• Improved hardness results for profit maximization pricing problems with unlimited supply
• On the hardness of pricing loss-leaders
• Approximation and competitive algorithms for single-minded selling problem
• Buying cheap is expensive: approximability of combinatorial pricing problems

Cited in

(13)

• On the complexity of the highway problem
• The envy-free pricing problem, unit-demand markets and connections with the network pricing problem
• Graph pricing with limited supply
• Buying cheap is expensive: approximability of combinatorial pricing problems
• How to Sell a Graph: Guidelines for Graph Retailers
• On the hardness of pricing loss-leaders
• Models and algorithms for the product pricing with single-minded customers requesting bundles
• Offline and online algorithms for single-minded selling problem
• Pricing loss leaders can be hard
• An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph
• Approximation algorithms and online mechanisms for item pricing
• Improved hardness results for profit maximization pricing problems with unlimited supply
• Approximation and competitive algorithms for single-minded selling problem

This page was built for publication: On Hardness of Pricing Items for Single-Minded Bidders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638879)