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

Weiwei Wu
, Minming Li^*
, Wanyong Tian
, Jason Chun Xue
, Enhong Chen

^*Corresponding author for this work

University of Science and Technology of China
City University of Hong Kong
USTC-CityU Joint Research Institute

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	89-98
Number of pages	10
Journal	Theoretical Computer Science
Volume	420
DOIs	https://doi.org/10.1016/j.tcs.2011.11.005
State	Published - 24 Feb 2012
Externally published	Yes

Keywords

Dynamic Storage Allocation
Multiple device
NP-completeness
Online algorithms

Access to Document

10.1016/j.tcs.2011.11.005

Cite this

@article{a2bb9305e67942cc856bc9cef2e34e37,

title = "Single and multiple device DSA problems, complexities and online algorithms",

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.",

keywords = "Dynamic Storage Allocation, Multiple device, NP-completeness, Online algorithms",

author = "Weiwei Wu and Minming Li and Wanyong Tian and Xue, \{Jason Chun\} and Enhong Chen",

year = "2012",

month = feb,

day = "24",

doi = "10.1016/j.tcs.2011.11.005",

language = "英语",

volume = "420",

pages = "89--98",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Single and multiple device DSA problems, complexities and online algorithms

AU - Wu, Weiwei

AU - Li, Minming

AU - Tian, Wanyong

AU - Xue, Jason Chun

AU - Chen, Enhong

PY - 2012/2/24

Y1 - 2012/2/24

N2 - 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.

AB - 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.

KW - Dynamic Storage Allocation

KW - Multiple device

KW - NP-completeness

KW - Online algorithms

UR - https://www.scopus.com/pages/publications/84856220964

U2 - 10.1016/j.tcs.2011.11.005

DO - 10.1016/j.tcs.2011.11.005

M3 - 文章

AN - SCOPUS:84856220964

SN - 0304-3975

VL - 420

SP - 89

EP - 98

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Single and multiple device DSA problems, complexities and online algorithms

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this