Improved results for a memory allocation problem
| dc.creator | Epstein, Leah | |
| dc.creator | van Stee, Rob | |
| dc.date | 2006-12-20 | |
| dc.date.accessioned | 2026-07-07T07:36:15Z | |
| dc.date.available | 2026-07-07T07:36:15Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0612100 | |
| dc.identifier | http://arxiv.org/abs/cs/0612100 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/120360 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | F.2.2 | |
| dc.title | Improved results for a memory allocation problem | |
| dc.type | text |