An improved algorithm for the minmax regret median problem on a tree

✍ Scribed by Igor Averbakh; Oded Berman

• Publisher: John Wiley and Sons
• Year: 2003
• Tongue: English
• Weight: 116 KB
• Volume: 41
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.10062

✦ Synopsis

Abstract

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.