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 evenFile 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.