You are here:
» An O(n log n) Version of the Averbakh-Berman Algorithm fo...
About Aarhus University
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 newspaper › Journal article › Research › peer-review
- Gerth Stølting Brodal
- Loukas Georgiadis, Denmark
- Irit Katriel, Denmark
- 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 language | English |
|---|---|
| Journal | Operations Research Letters |
| Volume | 36 |
| Issue | 1 |
| Pages (from-to) | 14 -18 |
| Number of pages | 5 |
| ISSN | 0167-6377 |
| DOIs | |
| Publication status | Published - 2008 |
- MinmaxRegret, Tree Median, Robust Optimization
Research areas
See relations at Aarhus University Citationformats
ID: 1294304