| The facility location problem is one of the most well-studied problems in optimization literature over the last four decades. Given a set of client locations, the problem seeks to find an optimal set of locations to build facilities (warehouses) minimizing the sum of the cost of building the facilities along with the cost of assigning clients (stores) to facilities. The assignment cost is often modeled by a weight times the metric distance. The facility location problem and its variant the k-median problem, which minimizes the assignment cost allowing at most k facilities, have been used in a variety of applications, for example network design, web-caching, and clustering. These problems are NP-hard, and have been studied from perspectives of empirical investigation of different heuristics, average-case analysis, polyhedral characterization and approximate heuristics with worst-case performance guarantees, among others.;These problems showcase some of the most interesting techniques in approximation algorithms, including local search, linear programming rounding, and primal-dual algorithms. We study these approaches and propose the first constant factor approximation for the k-median problem. We provide the best known approximation algorithms and the best known lower bounds for these two problems. We extend the techniques to solve different variants, incorporating capacities, fault-tolerance, hierarchical placement, and lower bounds on demand assigned to facilities.;We use these variants to provide the first constant factor approximation algorithm for single-sink edge-installation problem. This problem models a distribution network of utility companies and service providers. The problem minimizes the cost of designing a network which routes all the demand to a special sink node, where the cost per unit length of any edge obeys economies of scale and is a concave function of traffic through the edge.;Clustering large datasets, such as click streams, web pages, multimedia data, retail transactions, and telecommunication records, necessitate scalable algorithms that revisit data sparingly, and consume small space. We extend the k-median algorithms to the data-stream model, which only allows a single pass over the data with limited space. We use some of these approximation techniques to develop a robust hierarchical agglomerative clustering algorithm. |
