Abstract
We present a new algorithm for the discrete LAD curve-fitting problem for n points in k < eq n dimensional space. When k is about n/3 it begins to out-perform the best current methods, and the advantage increases with k. The algorithm should be of interest in approximation theory and in robust regression. Moreover our approach may be useful in linear optimization, especially in linear programming.