On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
From MaRDI portal
Publication:3068630
DOI10.1137/080735503zbMath1263.90037OpenAlexW2115435070MaRDI QIDQ3068630
Gagan Goel, Deeparnab Chakrabarty
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
Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Welfare economics (91B15)
Related Items (21)
An Improved Approximation Bound for Spanning Star Forest and Color Saving ⋮ Improved approximation algorithms for the spanning star forest problem ⋮ Approximating the Spanning k-Tree Forest Problem ⋮ Complexity and approximability of extended spanning star forest problems in general and complete graphs ⋮ A simple mechanism for a budget-constrained buyer ⋮ On the configuration LP for maximum budgeted allocation ⋮ Improved approximation for spanning star forest in dense graphs ⋮ Approximability of sparse integer programs ⋮ Local search algorithms for the maximum carpool matching problem ⋮ Generalized assignment problem: truthful mechanism design without money ⋮ On Variants of the Spanning Star Forest Problem ⋮ Truthful mechanism design via correlated tree rounding ⋮ APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM ⋮ Approximation for maximizing monotone non-decreasing set functions with a greedy method ⋮ Unnamed Item ⋮ On the star forest polytope for trees and cycles ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders ⋮ Truthful Generalized Assignments via Stable Matching ⋮ Limitations of Deterministic Auction Design for Correlated Bidders ⋮ Combinatorial auctions with endowment effect
This page was built for publication: On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
