On the configuration LP for maximum budgeted allocation

DOI10.1007/S10107-015-0928-8zbMATH Open1411.91335OpenAlexW2209447084MaRDI QIDQ896296FDOQ896296

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

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

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

• An approximation algorithm for the generalized assignment problem
• Geometric algorithms and combinatorial optimization.
• Gadgets, Approximation, and Linear Programming
• Non-approximability results for optimization problems on bounded degree instances
• Some optimal inapproximability results
• Approximation algorithms for scheduling unrelated parallel machines
• Combinatorial auctions with decreasing marginal utilities
• Dependent rounding and its applications to approximation algorithms
• The Santa Claus problem
• Santa Claus Schedules Jobs on Unrelated Machines
• A Parallel Repetition Theorem
• Improved Approximation Algorithms for Budgeted Allocations
• Title not available (Why is that?)
• On Allocating Goods to Maximize Fairness
• Santa Claus Meets Hypergraph Matchings
• On the Configuration-LP for Scheduling on Unrelated Machines
• Title not available (Why is that?)
• Budgeted Allocations in the Full-Information Setting
• Title not available (Why is that?)
• Algorithm Theory - SWAT 2004
• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP

Cited In (2)

• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
• Budgeted Allocations in the Full-Information Setting

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)