Approximation algorithms for multi-facility location

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.