On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP

DOI10.1137/080735503MaRDI QIDQ3068630zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

approximation algorithmslinear programsallocation problems

Mathematics Subject Classification ID

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)

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

Cited in

(29)

• Approximability of sparse integer programs
• Combinatorial auctions with endowment effect
• Improved approximation algorithms for the spanning star forest problem
• A simple mechanism for a budget-constrained buyer
• Approximation for maximizing monotone non-decreasing set functions with a greedy method
• Adwords in a panorama
• An improved approximation guarantee for the maximum budgeted allocation problem
• Approximating the Spanning k-Tree Forest Problem
• Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations
• 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
• Truthful generalized assignments via stable matching
• On the configuration LP for maximum budgeted allocation
• Approximation algorithms for a generalization of the maximum budget allocation
• Budgeted Allocations in the Full-Information Setting
• Generalized assignment problem: truthful mechanism design without money
• Approximating the spanning k-tree forest problem
• Polynomial-time approximation schemes for maximizing gross substitutes utility under budget constraints
• On the configuration LP for maximum budgeted allocation
• Weighted upper edge cover: complexity and approximability
• Local search algorithms for the maximum carpool matching problem
• Improved approximation for spanning star forest in dense graphs
• Polynomial-time approximation schemes for maximizing gross substitutes utility under budget constraints
• The average-value allocation problem
• 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)