An improved approximation guarantee for the maximum budgeted allocation problem

DOI10.1137/1.9781611974331.CH74MaRDI QIDQ4575654zbMATH OpenOpenAlexFDO

Authors Christos Kalaitzis

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.09293

Mathematics Subject Classification ID

Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: We study the Maximum Budgeted Allocation problem, which is the problem of assigning indivisible items to players with budget constraints. In its most general form, an instance of the MBA problem might include many different prices for the same item among different players, and different budget constraints for every player. So far, the best approximation algorithms we know for the MBA problem achieve a $3/4$-approximation ratio, and employ a natural LP relaxation, called the Assignment-LP. In this paper, we give an algorithm for MBA, and prove that it achieves a $3/4+c$-approximation ratio, for some constant $c>0$. This algorithm works by rounding solutions to an LP called the Configuration-LP, therefore also showing that the Configuration-LP is strictly stronger than the Assignment-LP (for which we know that the integrality gap is $3/4$) for the MBA problem.

Recommendations

• On the configuration LP for maximum budgeted allocation
• On the configuration LP for maximum budgeted allocation
• Approximation algorithms for a generalization of the maximum budget allocation
• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
• Budgeted Allocations in the Full-Information Setting

Cited in

(9)

• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
• Improved Approximation Algorithms for Budgeted Allocations
• Budgeted Allocations in the Full-Information Setting
• Approximation Schemes for Multi-Budgeted Independence Systems
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Approximation algorithms for a generalization of the maximum budget allocation
• On the configuration LP for maximum budgeted allocation
• Analysis of the Period Recovery Error Bound
• On the configuration LP for maximum budgeted allocation

This page was built for publication: An improved approximation guarantee for the maximum budgeted allocation problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575654)