A 1.52-Approximation Algorithm for the Uncapacitated Facility Location Problem

  • Mohammad Mahdian
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Applications - OR and Management Sciences, Production and Logistics, Supply Chain Management Tags Short URL: https://optimization-online.org/?p=9200

    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}.

    Citation

    Working Paper, MIT and the University of Iowa

    Article

    Download

    View A 1.52-Approximation Algorithm for the Uncapacitated Facility Location Problem