Bin covering with a general profit function: approximability results |
| |
Authors: | Attila Benkő György Dósa Zsolt Tuza |
| |
Institution: | 1. Department of Mathematics, University of Pannonia, Veszprém, Hungary 2. Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary 3. Department of Computer Science and Systems Technology, University of Pannonia, Veszprém, Hungary
|
| |
Abstract: | In the recent paper (Benk? et al. 2010) we introduced a new problem that we call Bin Packing/Covering with Delivery, or BP/CD for short. Mainly we mean under this expression that we look for not only a good, but a “good and fast” packing or covering. In the present paper we investigate the offline case. For the analysis, a novel view on “offline optimum” is introduced, which appears to be relevant concerning all problems where a final solution is ordering-dependent. We prove that if the item sizes are not allowed to be arbitrarily close to zero, then an optimal offline solution can be found in polynomial time. On the other hand, for unrestricted problem instances, no polynomial-time algorithm can achieve an asymptotic approximation ratio better than 6/7 if $P\ne NP$ . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|