Robust location problems with pos/neg weights on a tree

Robust location problems with pos/neg weights on a tree

0.00 Avg rating0 Votes
Article ID: iaor200392
Country: United States
Volume: 38
Issue: 2
Start Page Number: 102
End Page Number: 113
Publication Date: Sep 2001
Journal: Networks
Authors: ,
Keywords: obnoxious facilities
Abstract:

In this paper, we consider different aspects of robust 1-median problems on a tree network with uncertain or dynamically changing edge lengths and vertex weights which can also take negative values. The dynamic nature of a parameter is modeled by a linear function of time. A linear algorithm is designed for the absolute dynamic robust 1-median problem on a tree. The dynamic robust deviation 1-median problem on a tree with n vertices is solved in O(n2 α(n) log n) time, where α(n) is the inverse Ackermann function. Examples show that both problems do not possess the vertex optimality property. The uncertainty is modeled by given intervals, in which each parameter can take a value randomly. The absolute robust 1-median problem with interval data, where vertex weights might also be negative, can be solved in linear time. The corresponding deviation problem can be solved in O(n2) time.

Reviews

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