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

Gerth Stølting Brodal, Loukas Georgiadis, Irit Katriel

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

    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(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
    Volume36
    Issue1
    Pages (from-to)14 -18
    Number of pages5
    ISSN0167-6377
    DOIs
    Publication statusPublished - 2008

    Keywords

    • MinmaxRegret
    • Tree Median
    • Robust Optimization

    Fingerprint

    Dive into the research topics of 'An O(n log n) Version of the Averbakh-Berman Algorithm for the Robust Median of a Tree'. Together they form a unique fingerprint.

    Cite this