Bin packing with general cost structures

Details Bin packing with general cost structures Bin packing with general cost structures

2009-06-27

arxiv.org/abs/0906.5051v1

Computer Science

Data Structures and Algorithms

Scientific paper

Following the work of Anily et al., we consider a variant of bin packing, called "bin packing with general cost structures" (GCBP) and design an asymptotic fully polynomial time approximation scheme (AFPTAS) for this problem. In the classic bin packing problem, a set of one-dimensional items is to be assigned to subsets of total size at most 1, that is, to be packed into unit sized bins. However, in GCBP, the cost of a bin is not 1 as in classic bin packing, but it is a non-decreasing and concave function of the number of items packed in it, where the cost of an empty bin is zero. The construction of the AFPTAS requires novel techniques for dealing with small items, which are developed in this work. In addition, we develop a fast approximation algorithm which acts identically for all non-decreasing and concave functions, and has an asymptotic approximation ratio of 1.5 for all functions simultaneously.

Affiliated with

Also associated with

No associations

Rating

Bin packing with general cost structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bin packing with general cost structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bin packing with general cost structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-306153