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, 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.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/1110
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 30
  • ???jsp.display-item.citation.isi??? 27
social impact