On Two Dimensional Orthogonal Knapsack Problem

Details On Two Dimensional Orthogonal Knapsack Problem On Two Dimensional Orthogonal Knapsack Problem

2008-03-29

arxiv.org/abs/0803.4260v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper, we study the following knapsack problem: Given a list of squares with profits, we are requested to pack a sublist of them into a rectangular bin (not a unit square bin) to make profits in the bin as large as possible. We first observe there is a Polynomial Time Approximation Scheme (PTAS) for the problem of packing weighted squares into rectangular bins with large resources, then apply the PTAS to the problem of packing squares with profits into a rectangular bin and get a $\frac65+\epsilon$ approximation algorithm.

Affiliated with

Also associated with

No associations

Rating

On Two Dimensional Orthogonal Knapsack Problem 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 On Two Dimensional Orthogonal Knapsack Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Two Dimensional Orthogonal Knapsack Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-257461