Improved results for a memory allocation problem

Details Improved results for a memory allocation problem Improved results for a memory allocation problem

2006-12-20

arxiv.org/abs/cs/0612100v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider a memory allocation problem that can be modeled as a version of bin packing where items may be split, but each bin may contain at most two (parts of) items. A 3/2-approximation algorithm and an NP-hardness proof for this problem was given by Chung et al. We give a simpler 3/2-approximation algorithm for it which is in fact an online algorithm. This algorithm also has good performance for the more general case where each bin may contain at most k parts of items. We show that this general case is also strongly NP-hard. Additionally, we give an efficient 7/5-approximation algorithm.

Affiliated with

Also associated with

No associations

Rating

Improved results for a memory allocation 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 Improved results for a memory allocation problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved results for a memory allocation problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-241780