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

Igor Averbakh · Oded Berman

42 citations0/0 files storedNetworks

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Facility Location and Emergency Management Complexity and Algorithms in Graphs Optimization and Search Problems

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.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

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

Citations in this library

Citation map →

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

References

1997Robust Discrete Optimization and Its Applications 1998Robust Discrete Optimization and Its Applications.1971Optimal Center Location in Simple Networks 1998Minmax-regret robust 1-median location on a tree 2000Minmax Regret Median Location on a Network Under Uncertainty 2000Algorithms for the robust 1-center problem on a tree 1991Sensitivity Analysis in Minisum Facility Location Problems

Cited by

2008Minimax Regret Single-Facility Ordered Median Location Problems on Networks 2007A note on the minmax regret centdian location on trees 2014Minmax regret 1-facility location on uncertain path networks 2010A robust optimization model for p-median problem with uncertain edge lengths

Explore the map →

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

Imported from OpenAlex (CC0) — nothing here is generated.