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.
CAPRARA A., U. PFERSCHY (2004). Worst-Case Analysis of the Subset Sum Algorithm for Bin Packing. OPERATIONS RESEARCH LETTERS, 32, 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.
