Robust smoothed analysis of a condition number for linear programming (Q662310): Difference between revisions

A distinctive characteristic of the numerical analysis related computations is that they are affected by errors. To understand these errors the condition number of the input at hand is used, which is a positive number measuring the sensitivity of the output with respect to small perturbations of the input. This paper deals with the condition number of linear programs. More specifically, the paper performs, for the aforementioned class of problems, a smoothed analysis of the condition number introduced by Goffin and later generalised by Cucker and Cheung, stating and proving probability tail bounds for it under adversarial random perturbations.