  Increasingly, inheritance hierarchies are being used to reduce redundancy in
natural language processing lexicons. Systems that utilize inheritance
hierarchies need to be able to insert words under the optimal set of classes in
these hierarchies. In this paper, we formalize this problem for feature-based
default inheritance hierarchies. Since the problem turns out to be NP-complete,
we present an approximation algorithm for it. We show that this algorithm is
efficient and that it performs well with respect to a number of standard
problems for default inheritance. A prototype implementation has been tested on
lexical hierarchies and it has produced encouraging results. The work presented
here is also relevant to other types of default hierarchies.
