Questions tagged [smoothed-analysis]
The smoothed-analysis tag has no usage guidance.
7
questions
6
votes
1
answer
350
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,086
7
votes
1
answer
140
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
67
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
559
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
512
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
354
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
51
votes
6
answers
28k
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 ...
- 627