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.

Name thesis:degree_name

Master of Science (MS)

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

University of Nevada, Las Vegas

Year

2002

Author dc:creator

• Kodela, Prashanth

Contributors dc:contributor

• Laxmi Gewali

Statement dc:rights

• IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Language dc:language

English

Identifier

https://oasis.library.unlv.edu/rtds/1454

OAI identifier oai:identifier

oai:oasis.library.unlv.edu:rtds-2453