Approximation algorithms for imprecise computation tasks with 0/1 constraint

Joseph Y.T. Leung

Research output: Chapter in Book/Report/Conference proceedingChapter

1 Scopus citations


Meeting deadline constraints is of great importance in real-time systems. Sometimes, it is not feasible to schedule all the tasks so that they can meet their deadlines, a situation that occurs quite often when the system is saturated. In situations like this, it is often more desirable to execute some parts of every task, than to give up completely the execution of some tasks. The Imprecise Computation Model was introduced [1–3] to allow for the trade-off of the quality of computations in favor of meeting the deadline constraints. In this model, a task is logically decomposed into two subtasks, mandatory and optional. The mandatory subtask of each task is required to be completed by its deadline, while the optional subtask can be left unfinished. If a task has an unfinished optional subtask, it incurs an error equal to the execution time of its unfinished portion. The Imprecise Computation Model is extremely attractive in modeling iterative algorithms, where a task can be terminated prematurely with some loss of accuracy.

Original languageEnglish (US)
Title of host publicationHandbook of Approximation Algorithms and Metaheuristics
PublisherCRC Press
ISBN (Electronic)9781420010749
ISBN (Print)1584885505, 9781584885504
StatePublished - Jan 1 2007

All Science Journal Classification (ASJC) codes

  • General Computer Science


Dive into the research topics of 'Approximation algorithms for imprecise computation tasks with 0/1 constraint'. Together they form a unique fingerprint.

Cite this