Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

The Minmax Relative Regret Median Problem on Networks

The Minmax Relative Regret Median Problem on Networks 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). http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png INFORMS Journal on Computing INFORMS

The Minmax Relative Regret Median Problem on Networks

INFORMS Journal on Computing , Volume 17 (4): 11 – Nov 1, 2005
11 pages

Loading next page...
 
/lp/informs/the-minmax-relative-regret-median-problem-on-networks-wmAtw4fVgv

References (28)

Publisher
INFORMS
Copyright
Copyright © INFORMS
Subject
Research Article
ISSN
1091-9856
eISSN
1526-5528
DOI
10.1287/ijoc.1040.0080
Publisher site
See Article on Publisher Site

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).

Journal

INFORMS Journal on ComputingINFORMS

Published: Nov 1, 2005

Keywords: Keywords : analysis of algorithms ; networks ; facilities location

There are no references for this article.