A 1.52-Approximation Algorithm for the Uncapacitated Facility Location Problem

Mohammad Mahdian (mahdianmath.mit.edu)
Yinyu Ye (yinyu-yeuiowa.edu)
Jiawei Zhang (jiawei-zhanguiowa.edu)

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

Keywords: facility location problem

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Supply Chain Management )

Category 3: Applications -- OR and Management Sciences (Production and Logistics )

Citation: Working Paper, MIT and the University of Iowa

Download: [Postscript]

Entry Submitted: 01/23/2002
Entry Accepted: 01/23/2002
Entry Last Modified: 01/23/2002

Modify/Update this entry