Clustering algorithm analysis is a very well researched area. K-Means, K-Median and Spectral clustering are few types of these clustering algorithms where K-median clustering is a variation of K-means, where the objective is to minimize the distance from the set of given vertices to the set of chosen centers.
K-Median problem can be formulated to solve the Facility Location Problem. In this problem we are given a set of clients in metric space and we need assign all the clients to at least one of the facility closest to it among the given set of points to minimize the sum of cost of opening the facility and cost of connecting the clients to these facilities.
In this implementation project we implement at three algorithmic type approaches to solve facility location problem. • Local Search (1-Swap) K-Median heuristics. • Linear Programming with rounding (6 - Approximiation). • Linear Programming with rounding (4 - Approximiation).
Please find detailed report of this project in below document. https://github.com/Rahul664/EECS-279_Facility_Location/blob/main/final_report.pdf