Approximation algorithms for imprecise computation tasks with 0/1 constraint

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.