24
$\begingroup$

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?

$\endgroup$
6
  • 11
    $\begingroup$ Do people apply any sort of complexity analysis to their algorithms outside academia? $\endgroup$ Mar 7 '12 at 7:12
  • 2
    $\begingroup$ What @DaveClarke says; maybe he should ask for rigorous (or non-trivial) analyses. I expect many practitioners look at their algorithms, count the loop nesting depth and say: "This is $\cal{O}(n^3)$!". $\endgroup$
    – Raphael
    Mar 7 '12 at 7:15
  • 3
    $\begingroup$ While looking for any use of smoothed analysis other than Simplex I found a list curated by one of the guys who discovered the technique. $\endgroup$
    – Raphael
    Mar 7 '12 at 7:18
  • 1
    $\begingroup$ @DaveClarke how about people working at IBM or HP or NTT? Shouldn't they be using that kind of analysis? $\endgroup$ Mar 7 '12 at 9:31
  • 1
    $\begingroup$ @DaveClarke I do. $\endgroup$
    – Kevin
    Mar 7 '12 at 16:19
12
$\begingroup$

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")

$\endgroup$
2
  • 2
    $\begingroup$ The problem is that thus far, the big successes for smoothed analysis have been in explaining current practice, so the practitioners might merely react by saying "well that's nice that everything I've been doing can be shown to make sense" :). I don't know if someone decided to use a hitherto less-known heuristic BECAUSE of smoothed analysis. $\endgroup$
    – Suresh
    Mar 7 '12 at 18:14
  • $\begingroup$ Formal smoothed analysis is very difficult, there's no reason anyone not in theory should over practice it. On the other hand, if you consider it as a heuristic used to analyze an algorithm (namely, the input is semi-random), then it's probably used all the time. $\endgroup$ May 17 '12 at 23:42
3
$\begingroup$

The way people analyze algorithms in the real world is vastly different from academia. While in academia the goal is to find a provably-correct upper bound on the running time, in real life the goal is to understand how the algorithm works, and what tweaks can improve the running time. There are two main methods that are banned in academia but used in practice:

  • The method of approximation. Here you use a lot of simplifying assumptions to try to forecast the running time of an algorithm. Similar to what theoretical physicists (used to) do.
  • Experimentation. You run your algorithm and measure several statistics - how much time went to each part, how many times each function was called, how often was each branch run, and so on. This information can be used to optimize the algorithm. Experimentation is also used to find out whether some approximations done while analyzing the algorithm work in practice or not.

That said, I don't think that it's very common to analyze an algorithm in practice, other than to add some filler text in a related academic publication. The focus is either on software engineering or on low-level optimization, depending on the subject matter.

Finally, smoothed analysis is a heuristic that can be used to explain why algorithms work better in practice than their worst case would suggest - namely since some of the inputs are "random" in some sense. This heuristic can be used to approximate the behavior of the algorithm if one is using the method of approximation.

$\endgroup$
1
  • $\begingroup$ "While in academia the goal is to find a provably-correct upper bound on the running time" -- that is a goal, not the goal. There is also much work on average case analysis, even though the average CS student might not see much of it (because it is relatively hard). "To understand how the algorithm works" is, arguably, the basis of all algorithmics in academia. $\endgroup$
    – Raphael
    May 17 '12 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy