A Linear-Time Algorithm for Maxisum Facility Location on Tree Networks

1 February 1984

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science

Vol. 18 (1) , 76-84
https://doi.org/10.1287/trsc.18.1.76

Abstract

This 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²) required by a previously indicated procedure.

Keywords

BUILDING
DISTANCE
ALGORITHMS
OPTIMIZATION
TRANSPORTATION
FACILITY LOCATION
LOCATION
MATHEMATICAL MODELS
NETWORKS
COMPUTER PROGRAMMING

This publication has 0 references indexed in Scilit: