Single and multiple device DSA problems, complexities and online algorithms

Weiwei Wu; Minming Li; Wanyong Tian; Jason Chun Xue; Enhong Chen

doi:10.1016/j.tcs.2011.11.005

Single and multiple device DSA problems, complexities and online algorithms

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

Overview

View graph of relations

Author(s)

Weiwei Wu
Minming Li
Wanyong Tian
Jason Chun Xue
Enhong Chen

Related Research Unit(s)

Department of Computer Science

Detail(s)

Original language	English
Pages (from-to)	89-98
Journal / Publication	Theoretical Computer Science
Volume	420
Publication status	Published - 24 Feb 2012

Link(s)

DOI	DOI https://doi.org/10.1016/j.tcs.2011.11.005 Final Published version
	Check@CityULib
Link to Scopus	https://www.scopus.com/record/display.uri?eid=2-s2.0-84856220964&origin=recordpage
Permanent Link	https://scholars.cityu.edu.hk/en/publications/publication(49c1351e-9828-4200-ac44-2c9765920c5b).html

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.