The minimum covariance determinant (MCD) problem selects a fixed-cardinality subset of data points to minimize its sample covariance determinant. We develop approximation and exact algorithms and apply them to prediction residuals, using the mean and covariance of the selected subset to define ellipsoidal conformal regions. For rational data, quadratic-form selection yields a deterministic approximation scheme for the geometric mean of the covariance eigenvalues. Its running time is polynomial for fixed dimension and accuracy, with an exponent linear in the dimension at fixed accuracy. An affine-hull test solves instances with optimal value zero exactly. Zonotope enumeration yields an exact algorithm with polynomial bit complexity in fixed dimension, without a general-position assumption, and permits repeated observations and affine dependencies. Sampled versions of both constructions provide a hybrid initialization for branch-and-bound with spectral and completion lower bounds. We also derive two-sided bounds relating the optimal MCD value to minimum covering ellipsoid volume. Computational comparisons under common search rules and time limits show that the proposed node bounds increase the number of instances solved within numerical tolerances. Prediction experiments on synthetic, weather, and river-flow data show smaller calibrated region volumes, with empirical coverage evaluated alongside volume.
Citation
Wang, J., Xie, W. (2026). Computing the Minimum Covariance Determinant. Available at Optimization Online.