𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An approximation algorithm for the -level stochastic facility location problem

✍ Scribed by Zhen Wang; Donglei Du; Adriana F. Gabor; Dachuan Xu

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
268 KB
Volume
38
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the k-level stochastic facility location problem. For this, we present an LP rounding algorithm that is 3-approximate. This result is achieved by a novel integer linear programming formulation that exploits the stochastic structure.

πŸ“œ SIMILAR VOLUMES

An approximation algorithm for a facilit
An approximation algorithm for a facility location problem with stochastic demands and inventories
✍ A.F. Gabor; J.C.W. van Ommeren πŸ“‚ Article πŸ“… 2006 πŸ› Elsevier Science 🌐 English βš– 176 KB

We propose a 2-approximation algorithm for a facility location problem with stochastic demands. At open facilities, inventory is kept such that arriving requests find a zero inventory with (at most) some pre-specified probability. Costs incurred are expected transportation costs, facility operating

The approximation gap for the metric fac
The approximation gap for the metric facility location problem is not yet closed
✍ Jaroslaw Byrka; Karen Aardal πŸ“‚ Article πŸ“… 2007 πŸ› Elsevier Science 🌐 English βš– 150 KB

We consider the 1.52-approximation algorithm of Mahdian et al. for the metric uncapacitated facility location problem. We show that their algorithm does not close the gap with the lower bound on approximability, 1.463, by providing a construction of instances for which its approximation ratio is not