On the configuration LP for maximum budgeted allocation

DOI10.1007/s10107-015-0928-8zbMath1411.91335OpenAlexW2209447084MaRDI QIDQ896296

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

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Geometric algorithms and combinatorial optimization.
• An approximation algorithm for the generalized assignment problem
• Combinatorial auctions with decreasing marginal utilities
• The Santa Claus problem
• On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
• On the Configuration-LP for Scheduling on Unrelated Machines
• Improved Approximation Algorithms for Budgeted Allocations
• Santa Claus Meets Hypergraph Matchings
• Budgeted Allocations in the Full-Information Setting
• Dependent rounding and its applications to approximation algorithms
• A Parallel Repetition Theorem
• Gadgets, Approximation, and Linear Programming
• Santa Claus Schedules Jobs on Unrelated Machines
• On Allocating Goods to Maximize Fairness
• Non-approximability results for optimization problems on bounded degree instances
• Algorithm Theory - SWAT 2004
• Some optimal inapproximability results

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