We analyze the worst-case ratio of a natural heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. A known lower bound on the worst-case ratio of this heuristic is 1.6067..., conjectured to be tight. In this paper, we show a nontrivial upper bound of 4/3 + ln (4/3) = 1.6210..., thus determining the value of the worst-case ratio within a relative error smaller than 1%. We also discuss how the lower and upper bounds extend to the case in which the maximum item size is bounded.
Worst-Case Analysis of the Subset Sum Algorithm for Bin Packing / CAPRARA A.; U. PFERSCHY. - In: OPERATIONS RESEARCH LETTERS. - ISSN 0167-6377. - STAMPA. - 32:(2004), pp. 159-166. [10.1016/S0167-6377(03)00092-0]
Worst-Case Analysis of the Subset Sum Algorithm for Bin Packing
CAPRARA, ALBERTO;
2004
Abstract
We analyze the worst-case ratio of a natural heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. A known lower bound on the worst-case ratio of this heuristic is 1.6067..., conjectured to be tight. In this paper, we show a nontrivial upper bound of 4/3 + ln (4/3) = 1.6210..., thus determining the value of the worst-case ratio within a relative error smaller than 1%. We also discuss how the lower and upper bounds extend to the case in which the maximum item size is bounded.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
