Questions tagged [smoothed-analysis]

The tag has no usage guidance.

7
votes
1answer
106 views

Smoothed analysis to compare algorithms

Has there been any research using smoothed analysis to compare approximation algorithms that have the same approximation ratio? Any research that compares algorithms using smoothed analysis would be ...
1
vote
0answers
44 views

Average case or beyond worse case analysis for non-convex optimization procedures?

I'm not sure if this is a well-formed question or not, but I thought I would ask to see if anyone is aware of related literature. It is known that global optimization of non-convex functions is NP-...
12
votes
1answer
430 views

Smoothed analysis of approximation algorithms

Smoothed analysis has been applied many times to understand the runtime of exact algorithms for many problems like linear programming and k-means. There are fairly general results in this realm, for ...
16
votes
2answers
455 views

Paradigms for complexity analysis of algorithms

Worst-case and average case analysis are well-known measures for the complexity of an algorithm. Recently smoothed analysis has emerged as another paradigm to explain why some algorithms which are ...
9
votes
1answer
300 views

Smoothed Analysis: If a Problem has Pseudopolynomial Complexity, is it in Smooth P?

I have been facinated by the extraordinary explosion in Smoothed Analysis and was struck by a assertion in the paper Smoothed Analysis of Integer Programming. This stated that Integer Linear ...
31
votes
4answers
12k views

Complexity of the simplex algorithm

What is the upper bound on the simplex algorithm for finding a solution to a Linear Program? How would I go about finding a proof for such a case? It seems as though the worst case is if each vertex ...