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?

Improve this question
$\endgroup$
6
  • 11
    $\begingroup$ Do people apply any sort of complexity analysis to their algorithms outside academia? $\endgroup$
    – Dave Clarke
    Commented Mar 7, 2012 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
    Commented Mar 7, 2012 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
    Commented Mar 7, 2012 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$
    – Marcos Villagra
    Commented Mar 7, 2012 at 9:31
  • 1
    $\begingroup$ @DaveClarke I do. $\endgroup$
    – Kevin
    Commented Mar 7, 2012 at 16:19

2 Answers 2

Reset to default
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")

Improve this answer
$\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
    Commented Mar 7, 2012 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$
    – Yuval Filmus
    Commented May 17, 2012 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.

Improve this answer
$\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
    Commented May 17, 2012 at 23:52