Publisher: Springer Publishing Company
ISSN: 0022-3239
Source: Journal of Optimization Theory and Applications, Vol.112, Iss.3, 2002-03, pp. : 561-574
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
Using a few very basic observations, we proposed recently a direct and finite algorithm for the computation of the l^∞ regression line on a discrete set {(x_i, y_i)}^n_i under the assumption that x_1 lt x_2 lt ...x_n In this paper, we extend the algorithm to the case with at least one, possibly multiple y-values for each distinct x_i. Our algorithm finds all the regression lines in O(n^2) operations in the worst-case scenario and improves the existing best-known computational complexity result for this problem. Numerical results on random problems are included.