Single and multiple device DSA problems, complexities and online algorithms

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 ( log L ) -competitive algorithm for general jobs on multi-device Balancing DSA problems without any assumption.

Authors

• Weiwei Wu Department of Computer Science and Engineering, Southeast University
• Minming Li City University of Hong Kong
• Wanyong Tian
• Jason Chun Xue
• Enhong Chen School of Computer Science and Technology, University of Science and Technology of China, Hefei, China State Key Laboratory of Cognitive Intelligence, Hefei, China

Keywords

• Dynamic Storage Allocation
• Online algorithms
• Multiple device
• NP-completeness