| An O(n log n) Version of the Averbakh-Berman Algorithm for the Robust Median of a Tree ⋆ (2008) | |||||||||||||
Abstract | |||||||||||||
| Abstract. We show that the minmax regret median of a tree can be found in O(nlog n) time. This is obtained by a modification of Averbakh and Berman’s O(nlog 2 n)-time algorithm: We design a dynamic solution to their bottleneck subproblem of finding the middle of every root-leaf path in a tree. Keywords: Minmax Regret, Tree Median, Robust Optimization. 1 | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||