A set of items has to be assigned to a set of bins with size one. If necessary, the size of the bins can be extended. The objective is to minimize the total size, ie., the sum of the sizes of the bins. The Longest Processing Time-neuristic is applied to this NP-hard problem. For this approximation algorithm we prove a worst-case bound of 13/12 which is shown to be tight when the number of bins is even

A 13/12 Approximation Algorithm for Bin Packing with Extendable Bins / Dell'Olmo, Paolo; Kellerer, H.; Speranza, M. G.; Tuza, Z. S.. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - STAMPA. - 65:(1998), pp. 229-233.

A 13/12 Approximation Algorithm for Bin Packing with Extendable Bins

DELL'OLMO, Paolo;
1998

Abstract

A set of items has to be assigned to a set of bins with size one. If necessary, the size of the bins can be extended. The objective is to minimize the total size, ie., the sum of the sizes of the bins. The Longest Processing Time-neuristic is applied to this NP-hard problem. For this approximation algorithm we prove a worst-case bound of 13/12 which is shown to be tight when the number of bins is even
1998
APPROXIMATION ALGORITHMS; Bin Packing
01 Pubblicazione su rivista::01a Articolo in rivista
A 13/12 Approximation Algorithm for Bin Packing with Extendable Bins / Dell'Olmo, Paolo; Kellerer, H.; Speranza, M. G.; Tuza, Z. S.. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - STAMPA. - 65:(1998), pp. 229-233.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

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/11573/48629
 Attenzione

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

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