## Abstract

A fundamental facility location problem is to choose the location of facilities, such as industrial plants and warehouses, to minimize the cost of satisfying the demand for some commodity. There are associated costs for locating the facilities, as well as transportation costs for distributing the commodities. We assume that the transportation costs form a metric. This problem is commonly referred to as the uncapacitated facility location problem. Application to bank account location and clustering, as well as many related pieces of work, are discussed by Cornuejols, Nemhauser, and Wolsey. Recently, the first constant factor approximation algorithm for this problem was obtained by Shmoys, Tardos, and Aardal. We show that a simple greedy heuristic combined with the algorithm by Shmoys, Tardos, and Aardal, can be used to obtain an approximation guarantee of 2.408. We discuss a few variants of the problem, demonstrating better approximation factors for restricted versions of the problem. We also show that the problem is max SNP-hard. However, the inapproximability constants derived from the max SNP hardness are very close to one. By relating this problem to Set Cover, we prove a lower bound of 1.463 on the best possible approximation ratio, assuming NP ∉ DTIME[n^{O(log log n)}].

Original language | English (US) |
---|---|

Pages (from-to) | 228-248 |

Number of pages | 21 |

Journal | Journal of Algorithms |

Volume | 31 |

Issue number | 1 |

DOIs | |

State | Published - Apr 1999 |

### Funding

* A preliminary version of this paper appeared in the Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (1998). ²Supported by an ARO MURI Grant DAAH04-96-1-0007 and NSF Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. E-mail: [email protected]. ³ Research supported by NSF CAREER Award CCR-9501355. E-mail: [email protected].

## ASJC Scopus subject areas

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics