Abstract
We study the single-device Dynamic Storage Allocation (DSA) problem and the multi-device Balancing DSA problem in this paper. The goal is to dynamically allocate the job into memory to minimize the usage of space without concurrency. The SRF problem is just a variant of the DSA problem. Our results are as follows. The NP-completeness for the 2-SRF problem, 3-DSA problem, and DSA problem for jobs with agreeable deadlines.An improved 3-competitive algorithm for jobs with agreeable deadlines on single-device DSA problems. A 4-competitive algorithm for jobs with agreeable deadlines on multi-device Balancing DSA problems.Lower bounds for jobs with agreeable deadlines: any non-clairvoyant algorithm cannot be (2-)-competitive and any clairvoyant algorithm cannot be (1.54-)-competitive.The first O(logL)-competitive algorithm for general jobs on multi-device Balancing DSA problems without any assumption. © 2011 Elsevier B.V. All rights reserved.
| Original language | English |
|---|---|
| Pages (from-to) | 89-98 |
| Journal | Theoretical Computer Science |
| Volume | 420 |
| DOIs | |
| Publication status | Published - 24 Feb 2012 |
Research Keywords
- Dynamic Storage Allocation
- Multiple device
- NP-completeness
- Online algorithms
Fingerprint
Dive into the research topics of 'Single and multiple device DSA problems, complexities and online algorithms'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver