Smoothed analysis of left-to-right maxima with applications

Share/Save/Bookmark

Damerow, Valentina and Manthey, Bodo and Meyer auf der Heide, Friedhelm and Räcke, Heide Harald and Scheideler, Christian and Sohler, Christian and Tantau, Till (2012) Smoothed analysis of left-to-right maxima with applications. ACM Transactions on Algorithms, 8 (3). p. 30. ISSN 1549-6325

[img] PDF
Restricted to UT campus only
: Request a copy
562kB
Abstract:A left-to-right maximum in a sequence of n numbers $s_1, ..., s_n$ is a number that is strictly larger than all preceding numbers. In this paper we present a smoothed analysis of the number of left-to-right maxima in the presence of additive random noise. We show that for every sequence of $n$ numbers $s_i$ in $[0,1]$ that are perturbed by uniform noise from the interval $[-\epsilon,\epsilon]$, the expected number of left-to-right maxima is $\Theta(\sqrt{n/\epsilon} + \log n)$ for $\epsilon > 1/n.$ For Gaussian noise with standard deviation $\sigma$ we obtain a bound of $O((\log^{3/2} n)/ \sigma + \log n).$ We apply our results to the analysis of the smoothed height of binary search trees and the smoothed number of comparisons in the quicksort algorithm and prove bounds of $\Theta(\sqrt{n/\epsilon} + \log n)$ and $\Theta(\frac{n}{\epsilon+1} \sqrt{n/\epsilon} + n \log n)$, respectively, for uniform random noise from the interval $[-\epsilon,\epsilon]$. Our results can also be applied to bound the smoothed number of points on a convex hull of points in the two-dimensional plane and to smoothed motion complexity, a concept we describe in this paper. We bound how often one needs to update a data structure storing the smallest axis-aligned box enclosing a set of points moving in $d$-dimensional space.
Item Type:Article
Copyright:© ACM
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/80970
Official URL:http://doi.acm.org/10.1145/2229163.2229174
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page