 Indeed, the running time of the simplex method on input with noise is polynomial in the number of variables and the magnitude of the perturbations.Other algorithms for solving linear-programming problems are described in the linear-programming article.Another basis-exchange pivoting algorithm is the criss-cross algorithm.