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

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

2001-11-19

arxiv.org/abs/cs/0111050v7

Computer Science

Data Structures and Algorithms

Revised. Improved statement of main theorem

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-275050