A linear time algorithm for computing minmax regret 1-median on a tree network

DOI10.1007/s00453-013-9851-7zbMath1317.05182OpenAlexW2001915330MaRDI QIDQ486974

Zhao Song, Tsunehiko Kameda, Binay K. Bhattacharya

Publication date: 19 January 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9851-7

zbMATH Keywords

facility locationminmax regretrobust medianuncertain weights

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (7)

A linear time algorithm for the \(p\)-maxian problem on trees with distance constraint ⋮ Efficient algorithms for the minmax regret path center problem with length constraint on trees ⋮ A quadratic time exact algorithm for continuous connected 2-facility location problem in trees ⋮ Improved algorithms for computing minmax regret sinks on dynamic path and tree networks ⋮ An improved algorithm for the minmax regret path center problem on trees ⋮ Minimax regret 1-median problem in dynamic path networks ⋮ Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities

Cites Work

• An O\((n\log n)\) version of the Averbakh-Berman algorithm for the robust median of a tree
• Efficient algorithms for two generalized 2-median problems and the group median problem on trees
• Robust discrete optimization and its applications
• Location science research: a review
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Robust location problems with pos/neg weights on a tree
• A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• 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
• Computing Minmax Regret 1-Median on a Tree Network with Positive/Negative Vertex Weights
• Improved algorithms for the minmax-regret 1-center and 1-median problems

This page was built for publication: A linear time algorithm for computing minmax regret 1-median on a tree network