All opportunistic scheduling algorithms solve
simpler optimization problems at each scheduling instance
in order to achieve good long-term performance. The
analysis of these algorithms assumes that the simpler opti-
mization problems are solved exactly. However, in contrast,
real-life implementations only approximately solve these
problems but still yield close to optimal performance. We
formalize this observation by explicitly bounding the long-
term performance in terms of the error in the approxima-
tion made at every stage.