Name
Abstract | ||
|---|---|---|
We consider a version of the 1-median problem on a network with uncertain weights of nodes. For each node, only an interval estimate of its weight is known. It is required to find the minmax relative regret location, i.e., to minimize the worst-case ratio of the loss in the objective-function value (opportunity loss) that may occur because a decision is made without knowing which state of nature (scenario) will take place, to the best possible value of the objective function under the realized scenario. We present a polynomial O(mn3 log n) algorithm for this problem on a general network. We also present fast algorithms for networks with special structure (trees and paths). |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1287/ijoc.1040.0080 | INFORMS Journal on Computing |
Keywords | Field | DocType |
general network,present fast algorithm,opportunity loss,1-median problem,interval estimate,median problem,minmax relative regret,objective function,possible value,mn3 log n,minmax relative regret location,objective-function value,analysis of algorithms,networks | Discrete mathematics,Binary logarithm,Interval estimation,Mathematical optimization,Minimax,Polynomial,Regret,Analysis of algorithms,Mathematics,Opportunity cost | Journal |
Volume | Issue | ISSN |
17 | 4 | 1091-9856 |
Citations | PageRank | References |
4 | 0.42 | 16 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Igor Averbakh | 1 | 699 | 54.76 |