Aarhus University Seal

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

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Department of Computer Science
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(nlog2 n)-time algorithm: We design a dynamic solution to their bottleneck subproblem of finding the middle of every root-leaf path in a tree.
Original languageEnglish
JournalOperations Research Letters
Pages (from-to)14 -18
Number of pages5
Publication statusPublished - 2008

    Research areas

  • MinmaxRegret, Tree Median, Robust Optimization

See relations at Aarhus University Citationformats

ID: 1294304