Bin covering with a general profit function: approximability results

摘要: In the recent paper (Benkő et al. 2010) we introduced a new problem that call Bin Packing/Covering with Delivery, or BP/CD for short. Mainly mean under this expression look not only good, but “good and fast” packing covering. present investigate offline case. For analysis, novel view on “offline optimum” is introduced, which appears to be relevant concerning all problems where final solution ordering-dependent. We prove if item sizes are allowed arbitrarily close zero, then an optimal can found in polynomial time. On other hand, unrestricted instances, no polynomial-time algorithm achieve asymptotic approximation ratio better than 6/7 \(P\ne NP\).