The use of approximation as a method for dealing with complex problems is a fundamental research issue in Knowledge Representation. Using approximation in symbolic AI is not straightforward. Since many systems use some form of logic as representation, there is no obvious metric that tells us `how far' an approximate solution is from the correct solution. This article shows how to do a structured analysis of the use of an approximate entailment method for approximate problem solving, by combining theoretical with empirical analysis. We present a concrete case study of our approach: we use a generic approximate deduction method proposed by Cadoli and Schaerf to construct an approximate version of classification reasoning. We first derive theorems that characterise such approximate classification reasoning. We then present experiments that give further insights in the anytime behaviour of this approximate reasoning method.