Questions tagged [smoothed-analysis]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6 votes
1 answer
184 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 ...
user avatar
7 votes
1 answer
130 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 ...
user avatar
1 vote
0 answers
61 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-...
user avatar
12 votes
1 answer
527 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 ...
user avatar
16 votes
2 answers
495 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 ...
user avatar
  • 1,291
9 votes
1 answer
338 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 ...
user avatar
  • 1,558
45 votes
6 answers
22k 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 ...
user avatar
  • 567