✦ LIBER ✦

Analysis of a Local Search Heuristic for Facility Location Problems

✍ Scribed by Madhukar R. Korupolu; C.Greg Plaxton; Rajmohan Rajaraman

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 258 KB
Volume: 37
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1100

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we study approximation algorithms for several NP-hard facility location problems.We prove that a simple local search heuristic yields polynomialtime constant-factor approximation bounds for the metric versions of the uncapacitated k-median problem and the uncapacitated facility location problem.(For the k-median problem, our algorithms require a constantfactor blowup in the parameter k.) This local search heuristic was first proposed several decades ago, and has been shown to exhibit good practical performance in empirical studies. We also extend the above results to obtain constant-factor approximation bounds for the metric versions of capacitated k-median and facility location problems.

📜 SIMILAR VOLUMES

Note: A local-search heuristic for large

Note: A local-search heuristic for large set-covering problems

✍ Larry W. Jacobs; Michael J. Brusco 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 751 KB

Worst-case analysis of local search heur

Worst-case analysis of local search heuristics for the one-machine total tardiness problem

✍ Shiwei Chang; Hirofumi Matsuo; Guochun Tang 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 538 KB

Worst-case incremental analysis for a cl

Worst-case incremental analysis for a class of p-facility location problems

✍ R. L. Francis; T. J. Lowe; A. Tamir 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB 👁 1 views

A localization property for facility-loc

A localization property for facility-location problems with arbitrary norms

✍ Henrik Juel; Robert Love 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 189 KB

In an earlier article we showed that, for facilities-location problems characterized by generalized distance norms and any even number of existing facilities, the optimal location of the new facility is at the intersection of the lines joining the pairs of facilities if these lines intersect at a si