A note on the robust 1-center problem on trees

A note on the robust 1-center problem on trees

0.00 Avg rating0 Votes
Article ID: iaor20031310
Country: Netherlands
Volume: 110
Issue: 1
Start Page Number: 69
End Page Number: 82
Publication Date: Feb 2002
Journal: Annals of Operations Research
Authors: ,
Keywords: networks
Abstract:

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(n3 log n) time thus improving on Averbakh and Berman's algorithm with time complexity O(n6). 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 an Averbakh and Berman's time complexity of O(n2 log n).

Reviews

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