Smoothed analysis of left-to-right maxima with applications

DOI10.1145/2229163.2229174zbMATH Open1295.68233OpenAlexW2029151602MaRDI QIDQ3189072FDOQ3189072

Friedhelm Meyer auf der Heide, Valentina Damerow, Christian Sohler, Christian Scheideler, Bodo Manthey, Harald Räcke, Till Tantau

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2229163.2229174

Recommendations

• Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
• Smoothed analysis of binary search trees
• Algorithms and Computation
• Smoothed analysis. Motivation and discrete models
• Algorithms - ESA 2003

zbMATH Keywords

convex hullquicksortsmoothed analysisbinary search treesmotion complexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (5)

• On smoothed analysis of quicksort and Hoare's find
• Smoothed Analysis of Local Search Algorithms
• The multiplicity of left-to-right maxima in geometrically distributed words
• Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
• Smoothed analysis of partitioning algorithms for Euclidean functionals

This page was built for publication: Smoothed analysis of left-to-right maxima with applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189072)