An O\((n\log n)\) version of the Averbakh-Berman algorithm for the robust median of a tree
From MaRDI portal
Publication:924878
DOI10.1016/j.orl.2007.02.012zbMath1165.90656OpenAlexW2005183677MaRDI QIDQ924878
Loukas Georgiadis, Irit Katriel, Gerth Stølting Brodal
Publication date: 29 May 2008
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2007.02.012
Programming involving graphs or networks (90C35) Trees (05C05) Abstract computational complexity for mathematical programming problems (90C60)
Related Items (10)
Minmax regret for sink location on dynamic flow paths with general capacities ⋮ A quadratic time exact algorithm for continuous connected 2-facility location problem in trees ⋮ An improved algorithm for the minmax regret path centdian problem on trees ⋮ A minmax regret median problem on a tree under uncertain locations of the demand points ⋮ A linear time algorithm for computing minmax regret 1-median on a tree network ⋮ Lexicographicα-robustness: an application to the 1-median problem ⋮ Minimax regret 1-median problem in dynamic path networks ⋮ Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities ⋮ Minimax regret 1-sink location problem in dynamic path networks ⋮ On the minmax regret path median problem on trees
Cites Work
- A linear-time algorithm for a special case of disjoint set union
- On the computational power of pushdown automata
- Improved Algorithms for the Minmax Regret 1-Median Problem
- An Algorithmic Approach to Network Location Problems. II: Thep-Medians
- Efficiency of a Good But Not Linear Set Union Algorithm
- Minmax-regret robust 1-median location on a tree
- Minmax Regret Median Location on a Network Under Uncertainty
- An improved algorithm for the minmax regret median problem on a tree
This page was built for publication: An O\((n\log n)\) version of the Averbakh-Berman algorithm for the robust median of a tree
