The Near Exact Bin Covering Problem

We present a new generalization of the bin covering problem that is known to be a strongly NP-hard problem. In our generalization there is a positive constant \(\varDelta \) $\Delta$ , and we are given a set of items each of which has a positive size. We would like to find a partition of the items into bins. We say that a bin is near exact covered if the total size of items packed into the bin is between 1 and \(1+\varDelta \) $1+\Delta$ . Our goal is to maximize the number of near exact covered bins. If \(\varDelta =0\) $\Delta =0$ or \(\varDelta >0\) $\Delta >0$ is given as part of the input, our problem is shown here to have no approximation algorithm with a bounded asymptotic approximation ratio (assuming that \(P\ne NP\) $P\ne NP$ ). However, for the case where \(\varDelta >0\) $\Delta >0$ is seen as a constant, we present an asymptotic fully polynomial time approximation scheme (AFPTAS) that is our main contribution.