Packing items into several bins facilitates approximating the separable assignment problem

DOI10.1016/j.ipl.2015.02.001zbMath1328.68296WikidataQ57851339 ScholiaQ57851339MaRDI QIDQ2345851

Marco Bender, Stephan Westphal, Clemens Thielen

Publication date: 21 May 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.02.001

zbMATH Keywords

approximation algorithms; randomized rounding; separable assignment problem

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

68W25: Approximation algorithms

Related Items

Unnamed Item, Approximation algorithms for capacitated assignment with budget constraints and applications in transportation systems, The transportation problem with conflicts

Cites Work

• Assignment problems: a golden anniversary survey
• An approximation algorithm for the generalized assignment problem
• A \((1-1/e)\)-approximation algorithm for the generalized assignment problem
• Tight Approximation Algorithms for Maximum Separable Assignment Problems
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem