Tight approximation algorithms for maximum general assignment problems

DOI10.1145/1109557.1109624zbMath1192.90105OpenAlexW4234897719MaRDI QIDQ3581502

Michel X. Goemans, Lisa K. Fleischer, M. I. Sviridenko, Vahab S. Mirrokni

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109624

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items

An efficient approximation for the generalized assignment problem, Multiple subset sum with inclusive assignment set restrictions, Task assignment in tree-like hierarchical structures, Two stage decision making approach for Sensor Mission Assignment Problem, Min Sum Edge Coloring in Multigraphs Via Configuration LP, A Survey of the Generalized Assignment Problem and Its Applications, Coupled and \(k\)-sided placements: generalizing generalized assignment, Constrained Submodular Maximization via a Nonsymmetric Technique, Approximation schemes for generalized two-dimensional vector packing with application to data placement, Submodular optimization problems and greedy strategies: a survey, Budget-constrained cost-covering job assignment for a total contribution-maximizing platform, Unnamed Item, Tight Approximation Bounds for the Seminar Assignment Problem, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, Convergence and approximation in potential games, Distributed approximation of \(k\)-service assignment, Valuated matroid-based algorithm for submodular welfare problem, On the approximability of robust network design, Local search algorithms for the red-blue median problem, The generalized maximum coverage problem, On Lagrangian Relaxation and Subset Selection Problems, Performance bounds with curvature for batched greedy optimization, Flexible allocation on related machines with assignment restrictions, Robustly assigning unstable items, Online Submodular Maximization with Preemption, A priority based unbalanced time minimization assignment problem, A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints, On fractional cut covers, Truthful Generalized Assignments via Stable Matching, On a class of covering problems with variable capacities in wireless networks