Questions tagged [smoothed-analysis]
The smoothed-analysis tag has no usage guidance.
7
questions
7
votes
1
answer
365
views
Is there a simplex-like algorithm that can be used with a separation oracle?
Linear programs can be solved in polynomial time using the ellipsoid method, but in practice the Simplex method is much more efficient, and the smoothed analysis framework of Spielman and Teng ...
- 2,222
7
votes
1
answer
141
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
0
answers
69
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-...
- 161
12
votes
1
answer
565
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 ...
- 367
16
votes
2
answers
514
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 ...
- 1,311
9
votes
1
answer
356
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 ...
- 1,578
52
votes
6
answers
30k
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 ...
- 637