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

Abstract

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(n2). We present an algorithm with complexity O(n log2 n). © 2003 Wiley Periodicals, Inc.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 42 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.