A Linear-Time Algorithm for Maxisum Facility Location on Tree Networks
1984; Institute for Operations Research and the Management Sciences; Volume: 18; Issue: 1 Linguagem: Inglês
10.1287/trsc.18.1.76
ISSN1526-5447
Autores Tópico(s)Data Management and Algorithms
ResumoThis paper treats a topic in “obnoxious facility location,” namely the problem of locating a single facility in an n-vertex tree network so as to maximize the sum of its weighted distances from the vertices. It is shown that use of a suitable data structure permits a solution algorithm with computational effort O(n), an improvement over the O(n 2 ) required by a previously indicated procedure.
Referência(s)