The metric uncapacitated facility location problem : The problem and the approximation algorithms

Sammanfattning: The main purpose of this work is to present the basics and history of the metric uncapacitated facility location problem and give an introduction to the approximation algorithm of Vazirani, that gives an approximation guarantee of 3 for the optimal solution for the problem. Furthermore, the algorithm of Vazirani is demonstrated by an easy problem that shows the technicalities of the algorithm.