An O(nlogn) Version of the Averbakh-Berman Algorithm
for the Robust Median of a Tree

Gerth Stølting Brodal, Loukas Georgiadis and Irit Katriel

Abstract

Averbakh and Berman designed an algorithm for computing the minmax regret median of a tree in $O(n \log^2 n)$ time. The bottleneck of their algorithm is to identify, for each node $v$ of a weighted rooted tree, the \emph{middle node} which is halfway between $v$ and the root.  This computation takes $O(n\log n)$ time, and is repeated $O(\log n)$ times, where the tree is rooted at a different node each time.

We design a dynamic version of the middle node computation, which can recompute the middle nodes in linear time for all but a geometrically decreasing fraction of the tree. We show that with this modification, the Averbakh-Berman algorithm runs in $O(n\log{n})$ time.