Minimizing maximum weighted error for imprecise computation tasks

Kevin I.J. Ho; Joseph Y.T. Leung; W. D. Wei

doi:10.1006/jagm.1994.1020

Minimizing maximum weighted error for imprecise computation tasks

Kevin I.J. Ho
, Joseph Y.T. Leung
, W. D. Wei

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

17 Scopus citations

Abstract

We consider the problem of preemptively scheduling a set of imprecise computation tasks on m ≥ 1 identical processors, with each task T_i having two weights, w_i and w’_i. Two performance metrics are considered: (1) the maximum w’-weighted error; (2) the total w-weighted error subject to the constraint that the maximum w’-weighted error is minimized. For the problem of minimizing the maximum w’-weighted error, we give an algorithm which runs in O(n³ log²n) time for multiprocessors and O(n²) time for a single processor. For the problem of minimizing the total w-weighted error subject to the constraint that the maximum w’-weighted error is minimized, we give an algorithm which also has the same time complexity.

Original language	English (US)
Pages (from-to)	431-452
Number of pages	22
Journal	Journal of Algorithms
Volume	16
Issue number	3
DOIs	https://doi.org/10.1006/jagm.1994.1020
State	Published - May 1994
Externally published	Yes

All Science Journal Classification (ASJC) codes

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1006/jagm.1994.1020

Cite this

@article{95fd905a54f445c088fd0872a1e9f400,

title = "Minimizing maximum weighted error for imprecise computation tasks",

abstract = "We consider the problem of preemptively scheduling a set of imprecise computation tasks on m ≥ 1 identical processors, with each task Ti having two weights, wi and w{\textquoteright}i. Two performance metrics are considered: (1) the maximum w{\textquoteright}-weighted error; (2) the total w-weighted error subject to the constraint that the maximum w{\textquoteright}-weighted error is minimized. For the problem of minimizing the maximum w{\textquoteright}-weighted error, we give an algorithm which runs in O(n3 log2n) time for multiprocessors and O(n2) time for a single processor. For the problem of minimizing the total w-weighted error subject to the constraint that the maximum w{\textquoteright}-weighted error is minimized, we give an algorithm which also has the same time complexity.",

author = "Ho, \{Kevin I.J.\} and Leung, \{Joseph Y.T.\} and Wei, \{W. D.\}",

year = "1994",

month = may,

doi = "10.1006/jagm.1994.1020",

language = "English (US)",

volume = "16",

pages = "431--452",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Elsevier Inc.",

number = "3",

}

TY - JOUR

T1 - Minimizing maximum weighted error for imprecise computation tasks

AU - Ho, Kevin I.J.

AU - Leung, Joseph Y.T.

AU - Wei, W. D.

PY - 1994/5

Y1 - 1994/5

N2 - We consider the problem of preemptively scheduling a set of imprecise computation tasks on m ≥ 1 identical processors, with each task Ti having two weights, wi and w’i. Two performance metrics are considered: (1) the maximum w’-weighted error; (2) the total w-weighted error subject to the constraint that the maximum w’-weighted error is minimized. For the problem of minimizing the maximum w’-weighted error, we give an algorithm which runs in O(n3 log2n) time for multiprocessors and O(n2) time for a single processor. For the problem of minimizing the total w-weighted error subject to the constraint that the maximum w’-weighted error is minimized, we give an algorithm which also has the same time complexity.

AB - We consider the problem of preemptively scheduling a set of imprecise computation tasks on m ≥ 1 identical processors, with each task Ti having two weights, wi and w’i. Two performance metrics are considered: (1) the maximum w’-weighted error; (2) the total w-weighted error subject to the constraint that the maximum w’-weighted error is minimized. For the problem of minimizing the maximum w’-weighted error, we give an algorithm which runs in O(n3 log2n) time for multiprocessors and O(n2) time for a single processor. For the problem of minimizing the total w-weighted error subject to the constraint that the maximum w’-weighted error is minimized, we give an algorithm which also has the same time complexity.

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

UR - https://www.scopus.com/pages/publications/38149146598#tab=citedBy

U2 - 10.1006/jagm.1994.1020

DO - 10.1006/jagm.1994.1020

M3 - Article

AN - SCOPUS:38149146598

SN - 0196-6774

VL - 16

SP - 431

EP - 452

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 3

ER -

Minimizing maximum weighted error for imprecise computation tasks

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this