Average-case thresholds for exact regularization of linear programs

Michael P. Friedlander, Sharvaj Kubal, Yaniv Plan +1

Small regularizers can preserve linear programming solutions exactly. This paper provides the first average-case analysis of exact regularization: with a standard Gaussian cost vec…