The Remez algorithm is a well-known iterative routine to approximate a function by a polynomial in the minimax norm. But, as Nick Trefethen  says about it:
Most of these [implementations] go back many years and in fact, most of them do not solve the general best approximation problem as posed above but variants involving discrete variables or digital filtering. One can find a few other computer programs in circulation, but overall, it seems that there is no widely-used program at present for computing best approximations.
One can compute the minimax solution also by applying least-squares or convex optimization, for example using Matlab and the free CVX toolbox applied to the Runge function on [-1, 1]:
m = 101; n = 11; % 101 points, polynomial of degree 10 xi = linspace(-1, 1, m); % equidistant points in [-1, 1] ri = 1 ./ (1+(5*xi).^2); % Runge function tic % p is the polynomial of degree (n-1) cvx_begin % minimize the distance in all points variable p(n); minimize( max(abs(polyval(p, xi) - ri)) ); cvx_end toc % 0.17 sec for Matlab, CVX and SeDuMi
The approximation with Chebyshev polynomials has a minimax norm of
0.1090 while this approach here reaches a minimum of
0.0654, the same value that gets computed with the Remez algorithm in the Matlab
Is there any advantage in applying the more complicated Remez algorithm if you can compute the minimax solution faster and more accurate with an optimization solver? Are there any reports/articles comparing these two approaches on some difficult problems or test cases?
 R. Pachon and L. N. Trefethen. BIT Numerical Mathematics (2008) Vol. 46.