Master of Science (MS)
First Committee Member
Number of Pages
This thesis deals with the development and implementation of efficient algorithms to obtain acceptable solutions for the location of several facilities to serve customer sites. The general version of facility location problem is known to be NP-hard; For locating multiple facilities we use Voronoi diagram of initial facility locations to partition the customer sites into k clusters. On each Voronoi region, solutions for single facility problem is obtained by using both Weizfield's algorithm and Center of Gravity. The customer space is again partitioned by using the newly computed locations. This iteration is continued to obtain a better solution for multi-facility location problem. We call the resulting algorithm: "Voronoi driven k-median algorithm"; We report experimental results on several test data that include randomly distributed customers and distinctly clustered customers. The observed results show that the proposed approximation algorithm produces good results.
Algorithms; Approximation; Facility; Location
Computer science; Industrial engineering
University of Nevada, Las Vegas
If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to email@example.com and include clear identification of the work, preferably with URL.
Kodela, Prashanth, "Approximation algorithms for multi-facility location" (2002). UNLV Retrospective Theses & Dissertations. 1454.