Finding Minimum-Size Ellipsoids Covering a Subset of Points: Several Simple Heuristic Approaches
Pavel Sergeevich Shcherbakov · 2020
We propose several heuristic methods for finding an approximate solution to the following inherently combinatorial problem: Given N points in ℝn, construct the minimum- size ellipsoid covering exactly N - k of them, where k ≪ N. Various assumptions on the nature of the points and their amount are considered; the results of numerical experiments with the algorithms are discussed.