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

Gerth Stølting Brodal, Loukas Georgiadis, and Irit Katriel

In Operations Research Letters, volume 36(1), pages 14-18, 2008.

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² n)-time algorithm: We design a dynamic solution to their bottleneck subproblem of finding the middle of every root-leaf path in a tree.

Copyright notice

Copyright © 2008 by Elsevier Inc.. All rights reserved.

Online version

orl08.pdf (135 Kb)

DOI

10.1016/j.orl.2007.02.012

BIBT_EX entry

@article{orl08,
  author = "Gerth Stølting Brodal and Loukas Georgiadis and Irit Katriel",
  doi = "10.1016/j.orl.2007.02.012",
  issn = "0167-6377",
  journal = "Operations Research Letters",
  number = "1",
  pages = "14-18",
  title = "An $O(n\log n)$ Version of the Averbakh-Berman Algorithm for the Robust Median of a Tree",
  volume = "36",
  year = "2008"
}