Premium
Robust location problems with pos/neg weights on a tree
Author(s) -
Burkard Rainer E.,
Dollani Helidon
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.1029
Subject(s) - ackermann function , vertex (graph theory) , mathematics , combinatorics , function (biology) , interval (graph theory) , inverse , tree (set theory) , mathematical optimization , algorithm , graph , geometry , evolutionary biology , biology
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 ( n 2 α( 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 ( n 2 ) time. © 2001 John Wiley & Sons, Inc.