An O(nlogn) version of the Averbakh–Berman algorithm for the robust median of a tree

An O(nlogn) version of the Averbakh–Berman algorithm for the robust median of a tree

0.00 Avg rating—0 Votes
Article ID: iaor2009147
Country: Netherlands
Volume: 36
Issue: 1
Start Page Number: 14
End Page Number: 18
Publication Date: Jan 2008
Journal: Operations Research Letters
Authors: , ,
Keywords: Minimax regret
Abstract:

We show that the minmax regret median of a tree can be found in O(nlogn) time. This is obtained by a modification of Averbakh and Berman's O(nlog2n)-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.