# MPI-I-2003-1-018

## A note on the smoothed complexity of the single-source shortest path problem

### Schaefer, Guido

**MPI-I-2003-1-018**. November** **2003, 8 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

Banderier, Beier and Mehlhorn showed that the single-source shortest

path problem has smoothed complexity $O(m+n(K-k))$ if the edge costs are

$K$-bit integers and the last $k$ least significant bits are perturbed

randomly. Their analysis holds if each bit is set to $0$ or $1$ with

probability $\frac{1}{2}$.

We extend their result and show that the same analysis goes through for

a large class of probability distributions:

We prove a smoothed complexity of $O(m+n(K-k))$ if the last $k$ bits of

each edge cost are replaced by some random number chosen from $[0,

\dots, 2^k-1]$ according to some \emph{arbitrary} probability

distribution $\pdist$ whose expectation is not too close to zero.

We do not require that the edge costs are perturbed independently.

The same time bound holds even if the random perturbations are

heterogeneous.

If $k=K$ our analysis implies a linear average case running time for

various probability distributions.

We also show that the running time is $O(m+n(K-k))$ with high

probability if the random replacements are chosen independently.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 136 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-1-018

**BibTeX**
`@TECHREPORT{``Schaefer2003``,`

` AUTHOR = {Schaefer, Guido},`

` TITLE = {A note on the smoothed complexity of the single-source shortest path problem},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-2003-1-018},`

` MONTH = {November},`

` YEAR = {2003},`

` ISSN = {0946-011X},`

`}`