New Upper Bounds on The Approximability of 3D Strip Packing

Details New Upper Bounds on The Approximability of 3D Strip Packing New Upper Bounds on The Approximability of 3D Strip Packing

2006-07-22

arxiv.org/abs/cs/0607100v1

Computer Science

Data Structures and Algorithms

Submitted to SODA 2007

Scientific paper

In this paper, we study the 3D strip packing problem in which we are given a list of 3-dimensional boxes and required to pack all of them into a 3-dimensional strip with length 1 and width 1 and unlimited height to minimize the height used. Our results are below: i) we give an approximation algorithm with asymptotic worst-case ratio 1.69103, which improves the previous best bound of $2+\epsilon$ by Jansen and Solis-Oba of SODA 2006; ii) we also present an asymptotic PTAS for the case in which all items have {\em square} bases.

Affiliated with

Also associated with

No associations

Rating

New Upper Bounds on The Approximability of 3D Strip Packing 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 New Upper Bounds on The Approximability of 3D Strip Packing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Upper Bounds on The Approximability of 3D Strip Packing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-300981