Smoothed analysis

The simplex algorithm is a very efficient algorithm in practice, and it is one of the dominant algorithms for linear programming in practice. On practical problems, the number of steps taken by the algorithm is linear in the number of variables and constraints.[3][4] Yet in the theoretical worst case it takes exponentially many steps for most successfully analyzed pivot rules. This was one of the main motivations for developing smoothed analysis.[5]

For the perturbation model, we assume that the input data is perturbed by noise from a Gaussian distribution. For normalization purposes, we assume the unperturbed data ${\displaystyle {\bar {\mathbf {A} }}\in \mathbb {R} ^{n\times d},{\bar {\mathbf {b} }}\in \mathbb {R} ^{n},\mathbf {c} \in \mathbb {R} ^{d}}$ satisfies ${\displaystyle \|({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})\|_{2}\leq 1}$ for all rows ${\displaystyle ({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})}$ of the matrix ${\displaystyle ({\bar {\mathbf {A} }},{\bar {\mathbf {b} }}).}$ The noise ${\displaystyle ({\hat {\mathbf {A} }},{\hat {\mathbf {b} }})}$ has independent entries sampled from a Gaussian distribution with mean ${\displaystyle 0}$ and standard deviation ${\displaystyle \sigma }$. We set ${\displaystyle \mathbf {A} ={\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},\mathbf {b} ={\bar {\mathbf {b} }}+{\hat {\mathbf {b} }}}$. The smoothed input data consists of the linear program

maximize

${\displaystyle \mathbf {c^{T}} \cdot \mathbf {x} }$

subject to

${\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }$.

If the running time of our algorithm on data ${\displaystyle \mathbf {A} ,\mathbf {b} ,\mathbf {c} }$ is given by ${\displaystyle T(\mathbf {A} ,\mathbf {b} ,\mathbf {c} )}$ then the smoothed complexity of the simplex method is[6]

${\displaystyle C_{s}(n,d,\sigma ):=\max _{{\bar {\mathbf {A} }},{\bar {\mathbf {b} }},\mathbf {c} }~\mathbb {E} _{{\hat {\mathbf {A} }},{\hat {\mathbf {b} }}}[T({\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},{\bar {\mathbf {b} }}+{\hat {\mathbf {b} }},\mathbf {c} )]={\rm {poly}}(d,\log n,\sigma ^{-1}).}$

This bound holds for a specific pivot rule called the shadow vertex rule. The shadow vertex rule is slower than more commonly used pivot rules such as Dantzig's rule or the steepest edge rule[7] but it has properties that make it very well-suited to probabilistic analysis.[8]

A number of local search algorithms have bad worst-case running times but perform well in practice.[9]

One example is the 2-opt heuristic for the traveling salesman problem. It can take exponentially many iterations until it finds a locally optimal solution, although in practice the running time is subquadratic in the number of vertices.[10] The approximation ratio, which is the ratio between the length of the output of the algorithm and the length of the optimal solution, tends to be good in practice but can also be bad in the theoretical worst case.

One class of problem instances can be given by ${\displaystyle n}$ points in the box ${\displaystyle [0,1]^{d}}$, where their pairwise distances come from a norm. Already in two dimensions, the 2-opt heuristic might take exponentially many iterations until finding a local optimum. In this setting, one can analyze the perturbation model where the vertices ${\displaystyle v_{1},\dots ,v_{n}}$ are independently sampled according to probability distributions with probability density function ${\displaystyle f_{1},\dots ,f_{n}:[0,1]^{d}\rightarrow [0,\theta ]}$. For ${\displaystyle \theta =1}$, the points are uniformly distributed. When ${\displaystyle \theta >1}$ is big, the adversary has more ability to increase the likelihood of hard problem instances. In this perturbation model, the expected number of iterations of the 2-opt heuristic, as well as the approximation ratios of resulting output, are bounded by polynomial functions of ${\displaystyle n}$ and ${\displaystyle \theta }$.[10]

Another local search algorithm for which smoothed analysis was successful is the k-means method. Given ${\displaystyle n}$ points in ${\displaystyle [0,1]^{d}}$, it is NP-hard to find a good partition into clusters with small pairwise distances between points in the same cluster. Lloyd's algorithm is widely used and very fast in practice, although it can take ${\displaystyle e^{\Omega (n)}}$ iterations in the worst case to find a locally optimal solution. However, assuming that the points have independent Gaussian distributions, each with expectation in ${\displaystyle [0,1]^{d}}$ and standard deviation ${\displaystyle \sigma }$, the expected number of iterations of the algorithm is bounded by a polynomial in ${\displaystyle n}$, ${\displaystyle d}$ and ${\displaystyle \sigma }$. [11]