Robust smoothed analysis of a condition number for linear programming (Q662310)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6008688
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Robust smoothed analysis of a condition number for linear programming |
scientific article; zbMATH DE number 6008688 |
Statements
Robust smoothed analysis of a condition number for linear programming (English)
0 references
22 February 2012
0 references
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.
0 references
linear programming
0 references
condition numbers
0 references
smoothed analysis
0 references
perturbations
0 references
0 references
0 references
0.9008578658103944
0 references
0.8510004878044128
0 references
0.8258657455444336
0 references
0.8258653283119202
0 references
0.8251729011535645
0 references
