Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

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

Eduardo C. XavierFlàvio Keidi Miyazawa — 2009

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 note on dual approximation algorithms for class constrained bin packing problems

Eduardo C. XavierFlàvio Keidi Miyazawa — 2008

RAIRO - Theoretical Informatics and Applications

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 , and items of different classes, each item with class and size . 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...

A note on a two dimensional knapsack problem with unloading constraints

Jefferson Luiz Moisés da SilveiraEduardo Candido XavierFlávio Keidi Miyazawa — 2013

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

In this paper we address the two-dimensional knapsack problem with unloading constraints: we have a bin , and a list of rectangular items, each item with a class value in {1,...,}. The problem is to pack a subset of into , maximizing the total profit of packed items, where the packing must satisfy the unloading constraint: while removing one item , items with higher class values can not block . We present a (4 + )-approximation algorithm when the bin is a square. We also present (3 + )-approximation...

Page 1

Download Results (CSV)