Premium
An improved algorithm for the minmax regret median problem on a tree
Author(s) -
Averbakh Igor,
Berman Oded
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10062
Subject(s) - regret , minimax , tree (set theory) , node (physics) , mathematical optimization , mathematics , algorithm , function (biology) , interval (graph theory) , computer science , combinatorics , statistics , structural engineering , evolutionary biology , engineering , biology
We consider the 1‐median problem with uncertain weights for nodes. Specifically, for each node, only an interval estimate of its weight is known. It is required to find a “minmax regret” location, that is, to minimize the worst‐case loss in the objective function that may occur because the decision is made without knowing which state of nature will take place. For this problem on a tree, the best published algorithm has complexity O ( n 2 ). We present an algorithm with complexity O ( n log 2 n ). © 2003 Wiley Periodicals, Inc.