Name
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). (C) 2003 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1002/net.10062 | NETWORKS |
Keywords | Field | DocType |
minmax regret optimization,facility location,polynomial algorithms | Interval estimation,Combinatorics,Mathematical optimization,Minimax,Tree (graph theory),Algorithm complexity,Regret,Algorithm,Facility location problem,Combinatorial optimization,Polynomial algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
41 | 2 | 0028-3045 |
Citations | PageRank | References |
24 | 1.27 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Igor Averbakh | 1 | 699 | 54.76 |
| O. Berman | 2 | 1604 | 231.36 |