A fast asymptotic approximation scheme for bin packing with rejection

Bein, W; Correa JR; Han, X.

Abstract

"Bin packing with rejection" is the following problem: Given a list of items with associated sizes and rejection costs, find a packing into unit bins of a subset of the list such that the number of bins used plus the sum of rejection costs of unpacked items is minimized. We show that bin packing with rejection can be reduced to n multiple knapsack problems and, based on techniques for the multiple knapsack problem, we give a fast asymptotic polynomial time approximation scheme,"Reject&Pack", with time complexity O (nO (ε{lunate}- 2)). This improves a recent approximation scheme given by Epstein, which has time complexity O (nO ((ε{lunate}- 4)ε{lunate}- 1)). We also show that Reject&Pack can be extended to variable-sized bin packing with rejection and give an asymptotic polynomial time approximation scheme. © 2007 Elsevier Ltd. All rights reserved.

Más información

Título según WOS: A fast asymptotic approximation scheme for bin packing with rejection
Título según SCOPUS: A fast asymptotic approximation scheme for bin packing with rejection
Título de la Revista: THEORETICAL COMPUTER SCIENCE
Volumen: 393
Número: 01-mar
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2008
Página de inicio: 14
Página final: 22
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0304397507008146
DOI:

10.1016/j.tcs.2007.10.042

Notas: ISI, SCOPUS