𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree Network

✍ Scribed by Bhattacharya, Binay; Kameda, Tsunehiko; Song, Zhao

Book ID
121603358
Publisher
Springer
Year
2013
Tongue
English
Weight
738 KB
Volume
70
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Minmax-regret robust 1-median location o
Minmax-regret robust 1-median location on a tree
✍ Chen, Bintong; Lin, Chin-Shien πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 171 KB

This paper considers the minmax-regret 1-median problem on a tree network where edge lengths and node weights are uncertain and the uncertainty is characterized by given intervals. Some localization properties for the optimal locations, for both the node-restricted and the unrestricted cases, are de

An improved algorithm for the minmax reg
An improved algorithm for the minmax regret median problem on a tree
✍ Igor Averbakh; Oded Berman πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 116 KB πŸ‘ 1 views

## 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

Linear time algorithms for computing the
Linear time algorithms for computing the most reliable source on an unreliable tree network
✍ Xue, Guoliang πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 121 KB πŸ‘ 2 views

Given a tree network with n vertices where each edge has an operational probability, we are interested in finding a vertex on the tree whose expected number of reachable vertices is maximum. This problem was studied in Networks 27 (1996) 219-237, where an O(n 3 ) time algorithm and an O(n 2 ) time a