A note on dual approximation algorithms for class constrained bin packing problems

Xavier, Eduardo C. ; Miyazawa, Flàvio Keidi

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 2, pp. 239-248

Résumé

In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity $1$, and $n$ items of $Q$ different classes, each item $e$ with class $c_e$ and size $s_e$. The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size $d$. In a shelf bin packing problem, we have to obtain a shelf packing such that the total size of items and shelf divisors in any bin is at most 1. A dual approximation scheme must obtain a shelf packing of all items into $N$ bins, such that, the total size of all items and shelf divisors packed in any bin is at most $1+\epsilon$ for a given $\epsilon >0$ and $N$ is the number of bins used in an optimum shelf bin packing problem. Shelf divisors are used to avoid contact between items of different classes and can hold a set of items until a maximum given weight. We also present a dual approximation scheme for the class constrained bin packing problem. In this problem, there is no use of shelf divisors, but each bin uses at most $C$ different classes.

Détail

DOI : 10.1051/ita:2008027

Classification : 68W25
Keywords: bin packing, approximation algorithms