2-Median Problems in Tree Networks

Date created: 
2017-03-29
Identifier: 
etd10135
Keywords: 
Facility Location
2-median
Link-deletion
Path Partition
Abstract: 

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

Document type: 
Graduating extended essay / Research project
Rights: 
This thesis may be printed or downloaded for non-commercial research and scholarly purposes. Copyright remains with the author.
File(s): 
Senior supervisor: 
Binay Bhattacharyya
Ramesh Krishnamurthi
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Project) M.Sc.
Statistics: