Improved results for a memory allocation problem
<|reference_start|>Improved results for a memory allocation problem: 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.<|reference_end|>
@article{epstein2006improved,
    title={Improved results for a memory allocation problem},
    author={Leah Epstein and Rob van Stee},
    journal={arXiv preprint arXiv:cs/0612100},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0612100},
    primaryClass={cs.DS}
}