On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
DOI10.1137/080735503zbMATH Open1263.90037OpenAlexW2115435070MaRDI QIDQ3068630FDOQ3068630
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
Recommendations
- An improved approximation guarantee for the maximum budgeted allocation problem
- Approximation algorithms for a generalization of the maximum budget allocation
- On the configuration LP for maximum budgeted allocation
- On the configuration LP for maximum budgeted allocation
- Improved Approximation Algorithms for Budgeted Allocations
Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Approximation algorithms (68W25) Discrete location and assignment (90B80) Welfare economics (91B15)
Cited In (23)
- Approximability of sparse integer programs
- Improved approximation algorithms for the spanning star forest problem
- Combinatorial auctions with endowment effect
- Approximation for maximizing monotone non-decreasing set functions with a greedy method
- APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM
- A simple mechanism for a budget-constrained buyer
- Weighted Upper Edge Cover: Complexity and Approximability
- Adwords in a panorama
- Approximating the Spanning k-Tree Forest Problem
- Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations
- Title not available (Why is that?)
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- Limitations of Deterministic Auction Design for Correlated Bidders
- Generalized assignment problem: truthful mechanism design without money
- On Variants of the Spanning Star Forest Problem
- On the configuration LP for maximum budgeted allocation
- Improved approximation for spanning star forest in dense graphs
- Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
- Truthful Generalized Assignments via Stable Matching
- Local search algorithms for the maximum carpool matching problem
- Complexity and approximability of extended spanning star forest problems in general and complete graphs
- On the star forest polytope for trees and cycles
- Truthful mechanism design via correlated tree rounding
This page was built for publication: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068630)
