The bin packing problem consists of finding the minimum number of bins, of given capacity D, required to pack a set of objects, each having a certain weight. We consider the high-multiplicity version of the problem, in which there are only C different weight values. We show that when C = 2 the problem can be solved in time O(log D). For the general case, we give an algorithm which provides a solution requiring at most C − 2 bins more than the optimal solution, i.e., an algorithm that is asymptotically exact. For fixed C, the complexity of the algorithm is O(poly(log D)), where poly(·) is a polynomial function not depending on C.

Filippi, C., & Agnetis, A. (2005). An asymptotically exact algorithm for the high-multiplicity bin packing problem. MATHEMATICAL PROGRAMMING, 104, 21-37.

An asymptotically exact algorithm for the high-multiplicity bin packing problem

AGNETIS, ALESSANDRO
2005

Abstract

The bin packing problem consists of finding the minimum number of bins, of given capacity D, required to pack a set of objects, each having a certain weight. We consider the high-multiplicity version of the problem, in which there are only C different weight values. We show that when C = 2 the problem can be solved in time O(log D). For the general case, we give an algorithm which provides a solution requiring at most C − 2 bins more than the optimal solution, i.e., an algorithm that is asymptotically exact. For fixed C, the complexity of the algorithm is O(poly(log D)), where poly(·) is a polynomial function not depending on C.
Filippi, C., & Agnetis, A. (2005). An asymptotically exact algorithm for the high-multiplicity bin packing problem. MATHEMATICAL PROGRAMMING, 104, 21-37.
File in questo prodotto:
File Dimensione Formato  
An asymptotically exact algorithm for the high-multiplicity.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 213.28 kB
Formato Adobe PDF
213.28 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: http://hdl.handle.net/11365/17816
 Attenzione

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