{"id":{"repo_id":"unlv","oai_identifier":"oai:oasis.library.unlv.edu:rtds-2453"},"canonical_url":"https://search.dev.ndltd.org/etd/unlv/oai:oasis.library.unlv.edu:rtds-2453","repository":{"repo_id":"unlv","name":"University of Nevada - Las Vegas","base_url":"https://oasis.library.unlv.edu/do/oai/"},"display":{"title":"Approximation algorithms for multi-facility location","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Kodela, Prashanth"],"institution":"University of Nevada, Las Vegas","degree_name":"Master of Science (MS)","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Laxmi Gewali"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2002,"date_issued":"2002-01-01T08:00:00Z","date_published":"2002-01-01T08:00:00Z","updated_at":"2026-07-24T05:25:33Z","subjects":[],"languages":["English"],"rights":["IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://oasis.library.unlv.edu/rtds/1454"],"render_values":[{"text":"https://oasis.library.unlv.edu/rtds/1454","href":"https://oasis.library.unlv.edu/rtds/1454","code":true}]}]},"links":{"outbound_url":"https://doi.org/10.25669/rkrl-3f0w","outbound_label":"DOI","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Laxmi Gewali"]},{"key":"dc:creator","label":"Author","values":["Kodela, Prashanth"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:publisher","label":"Institution","values":["University of Nevada, Las Vegas"]},{"key":"dc:type","label":"Dc Type","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:rights","label":"Dc Rights","values":["IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["10.25669/rkrl-3f0w","https://oasis.library.unlv.edu/rtds/1454","https://oasis.library.unlv.edu/context/rtds/article/2453/viewcontent/uc.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["pdf"]},{"key":"dc:title","label":"Title","values":["Approximation algorithms for multi-facility location"]}]}],"canonical_facts":{"dc:contributor":["Laxmi Gewali"],"dc:creator":["Kodela, Prashanth"],"dc:description.abstract":["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."],"dc:format":["pdf"],"dc:identifier":["10.25669/rkrl-3f0w","https://oasis.library.unlv.edu/rtds/1454","https://oasis.library.unlv.edu/context/rtds/article/2453/viewcontent/uc.pdf"],"dc:language":["English"],"dc:publisher":["University of Nevada, Las Vegas"],"dc:rights":["IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/"],"dc:title":["Approximation algorithms for multi-facility location"],"dc:type":["Text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-07-24T05:25:33Z"}