2-Median Problems in Tree Networks

Date created
Facility Location Problems have a great significance for allocating resources efficiently in a network. The interaction mainly involves a price which depends on the distances between the objects and the order of significance of the objects(clients). The applications of such problems are immense in many application areas such as medical and transportation. In this project, we consider the p-median facility location problem in tree-networks. This p-median problem in general tree-networks is NP-hard. In this project, we have looked at efficiently solving the 2-median problem in tree networks. Using simple techniques of computational geometry, we give a O(n log s) time solution to the 2-median of a tree with s number of leaves. Our technique is then applied to solve other variants of the 2-median problem with the same complexity
Copyright statement
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Member of collection
Attachment Size
etd10135_RAcharyya.pdf 440.38 KB