Smoothed analysis of algorithms Why the simplex algorithm usually takes polynomial time.
We introduce the smoothed analysis of algorithms, which continuously interpolates between the worst-case and average-case analyses of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We me...
| Foilsithe in: | Journal of the ACM 51, 3 (2004). |
|---|---|
| Príomhchruthaitheoir: | |
| Formáid: | Alt |
| Teanga: | Béarla |
| Ábhair: |