论文标题
几乎确切的垃圾箱覆盖问题
The near exact bin covering problem
论文作者
论文摘要
我们提出了对垃圾箱覆盖问题的新概括，这被称为强烈的NP困难问题。在我们的概括中，有一个正常数$δ$，并且我们将获得一组项目，每个项目的大小为正。我们想找到将物品的分区分成垃圾箱。我们说，如果包装到垃圾箱中的物品的总尺寸在$ 1 $至$ 1+δ$之间，则垃圾桶几乎要覆盖。我们的目标是最大化近乎覆盖的垃圾箱的数量。如果$δ= 0 $或$δ> 0 $作为输入的一部分，则我们的问题在此显示没有近似算法，具有有限的渐近近似值（假设$ p \ neq np $）。但是，对于$δ> 0 $被视为常数的情况，我们提出了我们主要贡献的渐近完全多项式时间近似方案（AFPTA）。
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 $Δ$, 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+Δ$. Our goal is to maximize the number of near exact covered bins. If $Δ=0$ or $Δ>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\neq NP$). However, for the case where $Δ>0$ is seen as a constant, we present an asymptotic fully polynomial time approximation scheme (AFPTAS) that is our main contribution.
