MPII20031018
A note on the smoothed complexity of the singlesource shortest path problem
Schaefer, Guido
November 2003, 8 pages.
.
Status: available  back from printing
Banderier, Beier and Mehlhorn showed that the singlesource shortest
path problem has smoothed complexity $O(m+n(Kk))$ 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(Kk))$ if the last $k$ bits of
each edge cost are replaced by some random number chosen from $[0,
\dots, 2^k1]$ 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(Kk))$ with high
probability if the random replacements are chosen independently.

 Attachement: MPII20031018.ps (136 KBytes)
URL to this document: https://domino.mpiinf.mpg.de/internet/reports.nsf/NumberView/20031018
BibTeX
@TECHREPORT{Schaefer2003,
AUTHOR = {Schaefer, Guido},
TITLE = {A note on the smoothed complexity of the singlesource shortest path problem},
TYPE = {Research Report},
INSTITUTION = {MaxPlanckInstitut f{\"u}r Informatik},
ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPII20031018},
MONTH = {November},
YEAR = {2003},
ISSN = {0946011X},
}