Packing items into several bins facilitates approximating the separable assignment problem

In this paper, we consider the case of SAP where each item may be assigned at most k≥1 times (but at most once to each bin) and present a ((1−1ek)β)-approximation algorithm for this case under the assumption that the single bin subproblem admits a β-approximation algorithm. If the single bin subproblem admits an FPTAS, we obtain a (1−1ek)-approximation, which shows that, for k≥2, the problem admits approximation algorithms that beat the upper bound of (1−1e) known for other special cases of SAP.