An Absolute 2-Approximation Algorithm for Two-Dimensional Bin Packing

Details An Absolute 2-Approximation Algorithm for Two-Dimensional Bin Packing An Absolute 2-Approximation Algorithm for Two-Dimensional Bin Packing

2009-03-13

arxiv.org/abs/0903.2265v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the problem of packing rectangles into bins that are unit
squares, where the goal is to minimize the number of bins used. All rectangles
have to be packed non-overlapping and orthogonal, i.e., axis-parallel. We
present an algorithm for this problem with an absolute worst-case ratio of 2,
which is optimal provided P != NP.

Affiliated with

Also associated with

No associations

Rating

An Absolute 2-Approximation Algorithm for Two-Dimensional Bin 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 An Absolute 2-Approximation Algorithm for Two-Dimensional Bin Packing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Absolute 2-Approximation Algorithm for Two-Dimensional Bin Packing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-227982