Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SMOOTHED ANALYSIS:
Reports tagged with Smoothed Analysis:
TR05-063 | 24th June 2005
Bodo Manthey, Rüdiger Reischuk

#### Smoothed Analysis of the Height of Binary Search Trees

Revisions: 2

Binary search trees are one of the most fundamental data structures. While the
height of such a tree may be linear in the worst case, the average height with
respect to the uniform distribution is only logarithmic. The exact value is one
of the best studied problems in average case ... more >>>

TR06-023 | 7th February 2006
Xi Chen, Xiaotie Deng, Shang-Hua Teng

#### Computing Nash Equilibria: Approximation and Smoothed Complexity

By proving that the problem of computing a $1/n^{\Theta(1)}$-approximate Nash equilibrium remains \textbf{PPAD}-complete, we show that the BIMATRIX game is not likely to have a fully polynomial-time approximation scheme. In other words, no algorithm with time polynomial in $n$ and $1/\epsilon$ can compute an $\epsilon$-approximate Nash equilibrium of an \$n\times ... more >>>

TR07-039 | 27th March 2007
Bodo Manthey, Till Tantau

#### Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise

Revisions: 1

Binary search trees are a fundamental data structure and their height
plays a key role in the analysis of divide-and-conquer algorithms like
quicksort. Their worst-case height is linear; their average height,
whose exact value is one of the best-studied problems in average-case
complexity, is logarithmic. We analyze their smoothed height ... more >>>

TR13-008 | 7th January 2013