TY - GEN
T1 - Single and multiple device DSA problem, complexities and online algorithms
AU - Wu, Weiwei
AU - Tian, Wanyong
AU - Li, Minming
AU - Xue, Chun Jason
AU - Chen, Enhong
PY - 2010
Y1 - 2010
N2 - We study the single-device Dynamic Storage Allocation (DSA) problem and 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 DSA problem. Our results are as follows, • The NP-completeness for 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 problem. A 4-competitive algorithm for jobs with agreeable deadlines on multi-device Balancing DSA problem. • 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 problem without any assumption.
AB - We study the single-device Dynamic Storage Allocation (DSA) problem and 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 DSA problem. Our results are as follows, • The NP-completeness for 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 problem. A 4-competitive algorithm for jobs with agreeable deadlines on multi-device Balancing DSA problem. • 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 problem without any assumption.
UR - https://www.scopus.com/pages/publications/78650852905
U2 - 10.1007/978-3-642-17514-5_19
DO - 10.1007/978-3-642-17514-5_19
M3 - 会议稿件
AN - SCOPUS:78650852905
SN - 3642175163
SN - 9783642175169
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 218
EP - 229
BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings
T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
Y2 - 15 December 2010 through 17 December 2010
ER -