|
|||||
|
|
Computing the asymptotic worst-case of bin packing lower bounds |
|
| Authors: | Teodor Gabriel Crainic Guido Perboli Miriam Pezzuto Roberto Tadei |
| Institution: | 1. Département de management et technologie, U.Q.A.M., Centre de recherche sur les transports, U. de Montréal, C.P. 6128, Succursale Centre-ville – Montréal (QC), Canada H3C 3J7;2. Department of Control and Computer Engineering, Politecnico di Torino, Corso Duca degli Abruzzi, 24-I-10129 Torino, Italy |
| Abstract: | This paper addresses the issue of computing the asymptotic worst-case of lower bounds for the Bin Packing Problem. We introduce a general result that allows to bound the asymptotic worst-case performance of any lower bound for the problem and to derive for the first time the asymptotic worst-case of the well-known bound L3 by Martello and Toth. We also show that the general result allows to easily derive the asymptotic worst-case of several lower bounds proposed in the literature. |
| Keywords: | Packing Bin Packing lower bounds Asymptotic worst-case analysis |
| 本文献已被 ScienceDirect 等数据库收录！ | |