HackerPapers

arXiv:cs/0111050cs.DS

Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time

Daniel A. Spielman, Shang-Hua Teng

Abstract

We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis 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 measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity.

arXiv comments
Revised. Improved statement of main theorem
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 4 identifiable commenters in 4 comments across 4 threads, from Jan 2011 to Nov 2024. Found in 3 HN submissions from Feb 2008 to Mar 2016. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments4 threads

  1. Suits, money laundering, and linear programming 1 comment

    • Man, there was a lot of obtuse argument to wade through to get to this post. This is an interesting fact. Apparently this is the source? https://arxiv.org/abs/cs/0111050

      FooBarBizBazzView on HNParent context

  2. The Simplex Solution: Why it works so well 1 comment

    • The article discusses how the two mathematicians (Spielman and Teng) came up with Smoothed Analysis for Algorithms (as opposed to Worst case) which gives insight into why Simplex works well. We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case…

      npalliView on HNParent context

  3. Linear Programming: How Does It Work? 1 comment

    • > If you have tens of thousands of variables, you definitely don't want to risk dealing with the simplex method's worst-case behavior. The risk is extremely low. In fact, the risk is so low that, for deacdes, it was an open question why the simplex algorithm was so good in…

      luuView on HNParent context

  4. The polynomial algorithm for 3-SAT problem (or P=NP) 1 comment

    • OTOH, simplex is very efficient already. Average-case complexity for random matrices is polynomial, and there are some interesting results that extend beyond that (see http://arxiv.org/abs/cs/0111050).

      mzlView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.