Burkard, Rainer E.; Dollani, Helidon A note on the robust 1-center problem on trees. (English) Zbl 1013.90075 Ann. Oper. Res. 110, 69-82 (2002). Summary: 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)\). Cited in 15 Documents MSC: 90B80 Discrete location and assignment 90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) 90C35 Programming involving graphs or networks Keywords:location problems; robust optimization; center problem PDFBibTeX XMLCite \textit{R. E. Burkard} and \textit{H. Dollani}, Ann. Oper. Res. 110, 69--82 (2002; Zbl 1013.90075) Full Text: DOI