On the configuration LP for maximum budgeted allocation

DOI10.1007/S10107-015-0928-8MaRDI QIDQ896296zbMATH OpenOpenAlexFDO

Authors Christos Kalaitzis, Aleksander Mądry, Alantha Newman, Lukáš Poláček, Ola Svensson

Publication date 9 December 2015

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-07557-0_28

zbMATH Keywords

configuration LPmaximum budgeted allocation

Mathematics Subject Classification ID

Linear programming (90C05) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 5764783 (Why is no real title available?)
• scientific article; zbMATH DE number 5764883 (Why is no real title available?)
• scientific article; zbMATH DE number 1833405 (Why is no real title available?)
• A Parallel Repetition Theorem
• Algorithm Theory - SWAT 2004
• An approximation algorithm for the generalized assignment problem
• Approximation algorithms for scheduling unrelated parallel machines
• Budgeted Allocations in the Full-Information Setting
• Combinatorial auctions with decreasing marginal utilities
• Dependent rounding and its applications to approximation algorithms
• Gadgets, Approximation, and Linear Programming
• Geometric algorithms and combinatorial optimization.
• Improved Approximation Algorithms for Budgeted Allocations
• Non-approximability results for optimization problems on bounded degree instances
• On allocating goods to maximize fairness
• On the Configuration-LP for Scheduling on Unrelated Machines
• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
• Santa Claus Meets Hypergraph Matchings
• Some optimal inapproximability results
• The Santa Claus problem

Cited in

(6)

• How to sell hyperedges: the hypermatching assignment problem
• Budgeted Allocations in the Full-Information Setting
• Approximation algorithms for a generalization of the maximum budget allocation
• An improved approximation guarantee for the maximum budgeted allocation problem
• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
• On the configuration LP for maximum budgeted allocation

This page was built for publication: On the configuration LP for maximum budgeted allocation

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