Design and Analysis of Efficient Algorithms for the k-Supplier Problem

The k-supplier problem is a fundamental task in facility location and discrete optimization, where the objective is to select at most k facilities from a given set to minimize the maximum distance from any client to its nearest selected facility. While it is well-established that a 3-approximation is the best possible result for general metric spaces unless P = NP, geometric properties of specific spaces allow for improved bounds. This thesis investigates approximation algorithms for the k-supplier problem, with a primary focus on Euclidean spaces and their generalization to metric spaces with bounded doubling dimension. We explore a sqrt(1 + 3)-approximation algorithm for the Euclidean case and extend this logic to design a flexible approximation framework for constant doubling dimension spaces equipped with Minkowski metrics.