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 (30)

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

This page was built for publication: Tight approximation algorithms for maximum general assignment problems