The most widely accepted models of diagnostic reasoning are all phrased in terms of the logical consequence relations. In work in recent years, Schaerf and Cadoli have proposed efficient approximations of the classical consequence relation. The central idea of this paper is to parameterise the notion of diagnosis over different approximations of the consequence relation. This yields a number of different approximations of classical notions of diagnosis. We derive results about the relation between approximate and classical notions of diagnosis. Our results are attractive for a number of reasons. We obtain more flexible notions of diagnosis, which can be adjusted to particular situations. Furthermore, we obtain efficient anytime algorithms for computing both approximate and classical diagnoses.