Journal
ANNALS OF OPERATIONS RESEARCH
Volume 110, Issue 1-4, Pages 69-82Publisher
SPRINGER
DOI: 10.1023/A:1020711416254
Keywords
location problems; robust optimization; center problem
Categories
Ask authors/readers for more resources
We consider the robust 1-center problem on trees with uncertainty in vertex weights and edge lengths. The weights of the vertices and the lengths of the edges can take any value in prespecified intervals with unknown distribution. We show that this problem can be solved in O(n(3) log n) time thus improving on Averbakh and Berman's algorithm with time complexity O(n(6)). For the case when the vertices of the tree have weights equal to 1 we show that the robust 1-center problem can be solved in O(n log n) time, again improving on Averbakh and Berman's time complexity of O(n(2) log n).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available