Linear time algorithms for convex and monotone approximation

AbstractThis article presents algorithms of linear time complexity (O(n)) for computation of optimal solutions to the two problems of convex and monotone approximation where data points are approximated, respectively, by convex and monotone (nondecreasing) functions on a grid of (n + 1) points. For the convex approximation case, the algorithms are based on a linear programming approach which exploits the structure of matrices involved and uses a special pivoting procedure to obtain a “maximal” optimal solution. Analogously, in the monotone approximation case, the algorithms compute “maximal” and “minimal” optimal solutions which also “enclose” any other optimal solution between them. Computational results are presented