An exact polynomial time algorithm for computing the least trimmed squares estimate

An exact algorithm for computing the estimates of regression coefficients given by the least trimmed squares method is presented. The algorithm works under very weak assumptions and has polynomial complexity. Simulations show that in the case of two or three explanatory variables, the presented algorithm is often faster than the exact algorithms based on a branch-and-bound strategy whose complexity is not known. The idea behind the algorithm is based on a theoretical analysis of the respective objective function, which is also given.