Minimizing maximum weighted error for imprecise computation tasks

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

Research output: Contribution to journalArticlepeer-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 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.

Original languageEnglish (US)
Pages (from-to)431-452
Number of pages22
JournalJournal of Algorithms
Volume16
Issue number3
DOIs
StatePublished - May 1994

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Minimizing maximum weighted error for imprecise computation tasks'. Together they form a unique fingerprint.

Cite this