Consider the following Bin-Covering problem: Given n items with sizes a1, . . . , an ∈ (0, 1], maximize the number of bins opened so that each bin has items summing to at least 1. Give an asymptotic PTAS for this problem when restricted to instances in which item sizes are bounded below by c, for a fixed constant c > 0. (Hint: Use similar techniques as the PTAS algorithm for Bin-Packing problem)

Answer rating: 100% (QA)

We are given n objects of sizes s1s2 sn such that 0 si s 1 and an unlimited supply of unit sized bin... View the full answer