2010 | OriginalPaper | Buchkapitel
A Primal-Dual Approximation Algorithm for the k-Level Stochastic Facility Location Problem
verfasst von : Zhen Wang, Donglei Du, Dachuan Xu
Erschienen in: Algorithmic Aspects in Information and Management
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a
combinatorial
primal-dual 7-approximation algorithm for the
k
-level stochastic facility location problem, the stochastic counterpart of the standard
k
-level facility location problem. This approximation ratio is slightly worse than that of the primal-dual 6-approximation for the standard
k
-level facility location problem [3] because of the extra stochastic assumption. This new result complements the recent
non-combinatorial
3-approximation algorithm for the same problem by Wang et al [21].