Title: A linear algorithm for a minimax location of a path-shaped facility with a specific length in a weighted tree network

Authors: Abdallah W. Aboutahoun; Fatma El-Safty

Addresses: Department of Applied Mathematics and Information Science, Zewail City of Science and Technology, 6th of October City, Giza, Egypt; Department of Mathematics and Computer Science, Faculty of Science, Alexandria University, Alexandria, Egypt ' Department of Mathematics, Faculty of Science, Damanhour University, Damanhour, Egypt

Abstract: This paper considers the problem of locating a path-shaped facility of a specific size on a weighted tree network. The criterion for optimality used in this paper is the minimax criterion in which the weighted distance to the farthest vertex from the facility is minimised. The minimax criterion gives acceptable results from the point of view of the fast response for the clients who are located far away from the facility. This location problem usually has applications in computer science, information science, and operations research. An O(n) time algorithm is proposed for finding the optimal location of a path-shaped facility of a bounded length on a weighted tree network, where n is the number of vertices in the tree.

Keywords: tree network; facility location; minimax criterion; central path.

DOI: 10.1504/IJOR.2021.115626

International Journal of Operational Research, 2021 Vol.41 No.2, pp.218 - 225

Received: 03 Jun 2018
Accepted: 05 Aug 2018
Published online: 15 Jun 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article