A linear time algorithm for computing minmax regret 1-median on a tree network
type: Item
instance of: scholarly article
title: A linear time algorithm for computing minmax regret 1-median on a tree network
zbMATH Open document ID: 1317.05182
author: Tsunehiko Kameda
author: Zhao Song
author: Binay Bhattacharya
published in: Algorithmica
publication date: 2015-01-19T00:00:00Z
review text: The facility location problem is to minimize the communication or transportation costs. The cost function is formulated as the sum of distances from the nearest facility weighted by the weights of the vertices. The previous most efficient algorithm for finding minimum regret 1-median in a tree network with nonnegative vertex weights takes \(O(n\log n)\) time. The author's algorithm takes linear time, i.e. \(O(n)\).
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6387677
zbMATH Keywords: facility location
zbMATH Keywords: robust median
zbMATH Keywords: uncertain weights
zbMATH Keywords: minmax regret
MaRDI profile type: Publication
full work available at URL: s00453-013-9851-7
OpenAlex ID: W2001915330
cites work: Minmax Regret Median Location on a Network Under Uncertainty
cites work: An improved algorithm for the minmax regret median problem on a tree
cites work: A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree
cites work: Computing Minmax Regret 1-Median on a Tree Network with Positive/Negative Vertex Weights
cites work: An O\((n\log n)\) version of the Averbakh-Berman algorithm for the robust median of a tree
cites work: Robust location problems with pos/neg weights on a tree
cites work: Efficient algorithms for two generalized 2-median problems and the group median problem on trees
cites work: Minmax-regret robust 1-median location on a tree
cites work: Location science research: a review
cites work: An Algorithmic Approach to Network Location Problems. II: Thep-Medians
cites work: Robust discrete optimization and its applications
cites work: Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
cites work: An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
cites work: Improved algorithms for the minmax-regret 1-center and 1-median problems
DOI: 10.1007/S00453-013-9851-7
Recommended article: A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree
Recommended article: Computing Minmax Regret 1-Median on a Tree Network with Positive/Negative Vertex Weights
Recommended article: An improved algorithm for the minmax regret median problem on a tree
Recommended article: On the minmax regret path median problem on trees
Recommended article: Minmax-regret robust 1-median location on a tree
Recommended article: The Minmax Regret Reverse 1-Median Problem on Trees with Uncertain Vertex Weights
Recommended article: Improved algorithms for computing minmax regret sinks on dynamic path and tree networks
Recommended article: The minmax relative regret median problem on networks
Recommended article: Improved Algorithms for the Minmax Regret 1-Median Problem
Recommended article: A branch and bound algorithm for the minimax regret spanning arborescence
description: scientific article; zbMATH DE number 6387677