2006/12/20 by Leah Epstein, Epstein, Leah, Rob van Stee +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.cs/0612100
openalex publication_date 2006/12/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.