Physical Sciences and Mathematics Commons^™

Local Search Approximation Algorithms For Clustering Problems, Nasim Samei

Electronic Thesis and Dissertation Repository

In this research we study the use of local search in the design of approximation algorithms for NP-hard optimization problems. For our study we have selected several well-known clustering problems: k-facility location problem, minimum mutliway cut problem, and constrained maximum k-cut problem.

We show that by careful use of the local optimality property of the solutions produced by local search algorithms it is possible to bound the ratio between solutions produced by local search approximation algorithms and optimum solutions. This ratio is known as the locality gap.

The locality gap of our algorithm for the k-uncapacitated facility …