Case memory maintenance in a Case-Based Reasoning sys-tem is important for two main reasons: (1) to control the casememory size; (2) to reduce irrelevant and redundant instancesthat may produce inconsistencies in the Case-Based Reason-ing system. In this paper we present two approaches based ondeletion policies to the maintenance of case memories. Thefoundations of both approaches are the Rough Sets Theory,but each one applies a different policy to delete or maintaincases. The main purpose of these methods is to maintain thecompetence of the system and reduce, as much as possible,the size of the case memory. Experiments using different do-mains, most of them from the UCI repository, show that thereduction techniques maintain the competence obtained bythe original case memory. The results obtained are comparedwith those obtained using well-known reduction techniques.