A 1.52-Approximation Algorithm for the Uncapacitated Facility Location Problem
In this note we present an improved approximation algorithm for the (uncapacitated) metric facility location problem. This algorithm uses the idea of cost scaling, the greedy algorithm of \cite{JMS}, and the greedy augmentation procedure of \cite{CG,GK}. CitationWorking Paper, MIT and the University of IowaArticleDownload View PDF