Approximation algorithms for the partial assignment problem

DOI10.1016/j.tcs.2020.07.041zbMath1453.91054OpenAlexW3047111715MaRDI QIDQ2197546

Guichen Gao, Hing-Fung Ting, Yifei Zou, Yicheng Xu, Li Ning, Yong Zhang

Publication date: 1 September 2020

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

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

zbMATH Keywords

submodular functionvalue querypartial assignment

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Unnamed Item
• Unnamed Item
• Online pricing for bundles of multiple items
• Offline and online algorithms for single-minded selling problem
• Online Submodular Welfare Maximization
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• Online Lower Bounds via Duality
• Simple mechanisms for subadditive buyers via duality
• Reducibility among Combinatorial Problems
• Correlation-Robust Analysis of Single Item Auction
• Tight Revenue Gaps among Simple Mechanisms
• Pricing for Online Resource Allocation: Intervals and Paths

This page was built for publication: Approximation algorithms for the partial assignment problem