The Minmax Relative Regret Median Problem on Networks
INFORMS Journal on Computing · 2005 · Volume 17 · Issue 4
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 ( mn 3 log n ) algorithm for this problem on a general network. We also present fast algorithms for networks with special structure (trees and paths).
Keywords
analysis of algorithms, networks, facilities location
Enable JavaScript for citation tools and additional paper interactions.