Algorithms for the variable sized bin packing problem

Jangha Kang

doi:10.1016/S0377-2217(02)00247-3

Return

Algorithms for the variable sized bin packing problem

2003-06-01

142

PRE

Jangha Kang

Sungsoo Park

DOI：10.1016/S0377-2217(02)00247-3

Original

Original request for help

Save

Abstract

En 中文

In this paper, we consider the variable sized bin packing problem where the objective is to minimize the total cost of used bins when the cost of unit size, of each bin does not increase as the bin size increases. Two greedy algorithms are described, and analyzed in three special cases:.(a) the sizes of items and bins are divisible, respectively, (b) only the sizes of bins are divisible, and (c) the sizes of bins are not divisible. Here, we say that a list of numbers a(1), a(2),..., a(m) are divisible when a(j) exactly divides a(j-1), for each 1 < j less than or equal to m. In the case of (a), the algorithms give optimal solutions, and in the case of (b), each algorithm gives a solution whose value is less than 11/9C(B*) + 4 11/9, where C(B*) is the optimal value. In the case of (c), each algorithm gives a solution whose value is less than 3/2C(B*) + 1. (C) 2002 Elsevier Science B.V. All rights reserved.

Keywords:

algorithm

analysis of algorithm

combinatorial problem

packing

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.