On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
From MaRDI portal
Publication:3068630
DOI10.1137/080735503zbMath1263.90037MaRDI QIDQ3068630
Deeparnab Chakrabarty, Gagan Goel
Publication date: 17 January 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/080735503
90C05: Linear programming
90C59: Approximation methods and heuristics in mathematical programming
90B80: Discrete location and assignment
68W25: Approximation algorithms
91B32: Resource and cost allocation (including fair division, apportionment, etc.)
91B15: Welfare economics
Related Items
APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM, Truthful Generalized Assignments via Stable Matching, Approximating the Spanning k-Tree Forest Problem, Approximation for maximizing monotone non-decreasing set functions with a greedy method, Truthful mechanism design via correlated tree rounding, Approximability of sparse integer programs, On the configuration LP for maximum budgeted allocation, Improved approximation for spanning star forest in dense graphs, Improved approximation algorithms for the spanning star forest problem, Limitations of Deterministic Auction Design for Correlated Bidders, On Variants of the Spanning Star Forest Problem, An Improved Approximation Bound for Spanning Star Forest and Color Saving
