Back to Search
Start Over
Single and multiple device DSA problems, complexities and online algorithms
- Source :
-
Theoretical Computer Science . Feb2012, Vol. 420, p89-98. 10p. - Publication Year :
- 2012
-
Abstract
- 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 -competitive and any clairvoyant algorithm cannot be -competitive. [•] The first -competitive algorithm for general jobs on multi-device Balancing DSA problems without any assumption. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 420
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 71253707
- Full Text :
- https://doi.org/10.1016/j.tcs.2011.11.005