Approximation algorithms for facility location problems

David B. Shmoys, Éva Tardos, Karen Aardal

Data Archiving and Networked Services (DANS) · 1997 · 508 citations · 0 references

Full text

Open access

Concepts

Abstract

One of the most flourishing areas of research in the design and analysis of approximation algorithms has been for facility location problems. In particular, for the metric case of two simple models, the uncapacitated facility location and the k-median problems, there are now a variety of techniques that yield constant performance guarantees. These methods