Robust location problems with Pos/Neg weights on a tree

In this paper, we consider different aspects of robust 1-median problems on a tree network with uncertain or dynamically changing edge lengths and ver tex weights which can also take negative values. The dynamic nature of a pa rameter is modeled by a linear function of time. A linear algorithm is desi gned for the absolute dynamic robust 1-median problem on a tree. The dynami c robust deviation 1-median problem on a tree with n vertices is solved in O(n(2) alpha (n) log n) time, where alpha (n) is the inverse Ackermann func tion. Examples show that both problems do not possess the vertex optimality property. The uncertainty is modeled by given intervals, in which each par ameter 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(n(2) ) time. (C) 2001 John Wiley & Sons, Inc.