Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [smoothed-analysis]

The tag has no usage guidance.

4
votes
0answers
59 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
43 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
410 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
452 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
296 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
11k 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 ...