An O(n log n) version of the Averbakh-Berman algorithm for the robust median of a tree

An O(n log n) version of the Averbakh-Berman algorithm for the robust median of a tree

0.00 Avg rating0 Votes
Article ID: iaor20102807
Volume: 36
Issue: 1
Start Page Number: 14
End Page Number: 18
Publication Date: Jan 2008
Journal: Operations Research Letters
Authors: , ,
Abstract:

We show that the minmax regret median of a tree can be found in O(n log n) time. This is obtained by a modification of Averbakh and Berman's O(n log2n)-time algorithm: we design a dynamic solution to their bottleneck subproblem of finding the middle of every root-leaf path in a tree.

Reviews

Required fields are marked *. Your email address will not be published.