On the minimax approximation in the class of the univariate piecewise constant functions (Q1195872)

Let \(F(I)\) be the class of univariate piecewise constant functions with a finite number of constant pieces defined on a real interval \(I\). For \(g\in F(I)\), let \(S(g)\) denote the number of constant pieces of \(g\). This work involves the best uniform approximation of an \(f\in F(I)\) from the subclass of \(F(I)\) consisting of functions \(g\) with \(S(g)\leq k\) for some fixed \(k\). There are also associated mathematical programming and minimum path formulations. It is shown that optimal solutions exist. Algorithms for finding optimal solutions are defined and bounds are proven for the number of steps needed to obtain a solution.