Packing items into several bins facilitates approximating the separable assignment problem
( ( 1 ? 1 e k ) ? ) -approximation for k-SAP if the single bin problem admits a ?-approximation. ( 1 ? 1 e k ) -approximation for k-SAP if the single bin problem admits an FPTAS. For k?2 k ? 2 , our algorithm beats the upper bound of ( 1 ? 1 e ) known for other special cases of SAP.
separable assignment problem approximation algorithms randomized rounding