patternModerate
Is Smoothed Analysis used outside academia?
Viewed 0 times
academiausedanalysisoutsidesmoothed
Problem
Did the smoothed analysis find its way into main stream analysis of algorithms? Is it common for algorithm designers to apply smoothed analysis to their algorithms?
Solution
I could be wrong, but I view smoothed analysis as a way to explain the in-practice behaviour of algorithms that have bad theoretical guarantees (simplex, k-means, and so on). I'm not sure what it would mean to use smoothed analysis in practice, except to justify the use of a particular heuristic with bad worst-case performance ("My heuristic has blah blah worst-case behaviour but a smoothed analysis indicates that it will do well in practice etc etc")
Context
StackExchange Computer Science Q#74, answer score: 12
Revisions (0)
No revisions yet.