We propose six heuristic methods for finding an approximate solution to the following combinatorial problem: GivenN points in the n-dimensional space, find the minimum-size ellipsoid covering exactly N-k of them, where k is much less than N. Various assumptions on the nature of the points and their amount are considered; the results of illustrative numerical experiments with the algorithms are discussed.