An O(n log n) version of the Averbakh-Berman algorithm for the robust median of a tree
Loading...
Date
Authors
Brodal, G.
Georgiadis, L.
Katriel, I.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Type
Type of the conference item
Journal type
peer reviewed
Educational material type
Conference Name
Journal name
Operations Research Letters
Book name
Book series
Book edition
Alternative title / Subtitle
Description
We show that the minmax regret median of a tree can be found in O(n log n) time. This is obtained by a modification of Averbakh and Berman's O(n log(2) n)-time algorithm: we design a dynamic solution to their bottleneck subproblem of finding the middle of every root-leaf path in a tree. (c) 2007 Elsevier B.V. All rights reserved.
Description
Keywords
minmax regret, tree median, robust optimization, set union, location, network
Subject classification
Citation
Link
Language
en
Publishing department/division
Advisor name
Examining committee
General Description / Additional Comments
Institution and School/Department of submitter
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής