AbstractWe investigate the total least square problem (TLS) with Chebyshev norm instead of the traditionally used Frobenius norm. The use of Chebyshev norm is motivated by the need for robust solutions. In order to solve the problem, we introduce interval computation and use many of the results obtained there. We show that the problem we are tackling is NP-hard in general, but it becomes polynomial in the case of a fixed number of regressors. This is the most important practical result since usually we work with regression models with a low number of regression parameters (compared to the number of observations). We present not only a precise algorithm for the problem, but also a computationally efficient heuristic. We illustrate the behavior of our method in a particular probabilistic setup by a simulation study.