Algorithms for the robust 1‐center problem on a tree

Algorithms for the robust 1‐center problem on a tree

0.00 Avg rating0 Votes
Article ID: iaor2001636
Country: Netherlands
Volume: 123
Issue: 2
Start Page Number: 292
End Page Number: 302
Publication Date: Jun 2000
Journal: European Journal of Operational Research
Authors: ,
Keywords: networks: flow
Abstract:

We consider the weighted 1‐center problem on a network with uncertainty in node weights and edge lengths. Uncertainty is modelled by means of interval estimates for parameters. Specifically, each uncertain parameter is assumed to be random with unknown distribution and can take on any value within a corresponding prespecified interval. It is required to find a robust (minmax regret) solution, that is, a location which is ε‐optimal for any possible realization of parameters, with ε as small as possible. The problem on a general network is known to be NP‐hard; for the problem on a tree, we present a polynomial algorithm.

Reviews

Required fields are marked *. Your email address will not be published.