Offline and online algorithms for single-minded selling problem

DOI10.1016/j.tcs.2020.03.017zbMath1437.91229MaRDI QIDQ2173298

Sheung-Hung Poon, Yong Zhang, Francis Y. L. Chin, Hing-Fung Ting, Dongxiao Yu, Da-Chuan Xu

Publication date: 22 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.03.017

zbMATH Keywords

competitive ratio; NP-hardness; approximation ratio; single-minded selling

Mathematics Subject Classification ID

91B26: Auctions, bargaining, bidding and selling, and other market models

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

Related Items

EFX under budget constraint, Models and algorithms for the product pricing with single-minded customers requesting bundles, Approximation algorithms for the partial assignment problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Average-case competitive analyses for one-way trading
• Online pricing for bundles of multiple items
• Competitive algorithms for unbounded one-way trading
• Constant competitive algorithms for unbounded one-way trading under monotone hazard rate
• Dynamic pricing for impatient bidders
• Optimal Envy-Free Pricing with Metric Substitutability
• Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply
• Reducibility among Combinatorial Problems
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
• Optimal search and one-way trading online algorithms