Smoothed analysis of binary search trees
From MaRDI portal
Publication:2371805
DOI10.1016/j.tcs.2007.02.035zbMath1120.68043OpenAlexW2157661221MaRDI QIDQ2371805
Bodo Manthey, K. Ruediger Reischuk
Publication date: 9 July 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.035
Related Items (9)
Smoothed Analysis of Local Search Algorithms ⋮ On Smoothed Analysis of Quicksort and Hoare’s Find ⋮ An Improved Bound for Random Binary Search Trees with Concurrent Insertions ⋮ Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design ⋮ Universality for Eigenvalue Algorithms on Sample Covariance Matrices ⋮ On smoothed analysis of quicksort and Hoare's find ⋮ Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise ⋮ Smoothed analysis of balancing networks ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On growing random binary trees
- Generating quasi-random sequences from semi-random sources
- Smoothed analysis of termination of linear programming algorithms
- Heuristics for semirandom graph problems
- Constant bounds on the moments of the height of binary search trees
- An analytic approach to the height of binary search trees
- Randomized search trees
- Topology matters: smoothed competitiveness of metrical task systems
- The height of a random binary search tree
- An analytic approach to the height of binary search trees II
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Smoothed analysis of algorithms
- Smoothed Analysis of Integer Programming
- A note on the height of binary search trees
- On the concentration of the height of binary search trees
- Coloring Random and Semi-Random k-Colorable Graphs
- On the Variance of the Height of Random Binary Search Trees
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm
- Mathematical Foundations of Computer Science 2003
- Algorithms – ESA 2004
- Typical Properties of Winners and Losers [0.2ex in Discrete Optimization]
- Fundamentals of Computation Theory
- Algorithms - ESA 2003
- Algorithms and Data Structures
This page was built for publication: Smoothed analysis of binary search trees