The Least-trimmed-squares (LTS) estimator is a well known robust estimator in terms of protecting the estimate from the outliers. Its high computational complexity is however a problem in practice. In this paper, we propose a random LTS algorithm which has a low computational complexity that can be calculated a priori as a function of the required error bound and the confidence interval. Moreover, if the number of data points goes to infinite, the algorithm becomes a deterministic one that converges to the true LTS in some probability sense. (C) 2003 Elsevier Ltd. All rights reserved.