An Approximation Algorithm for the Risk-Adjusted Two-Stage Stochastic Facility Location Problem with Penalties

被引：3

作者：

Shao J. ^{[1
]}

Xu D. ^{[1
]}

机构：

[1] Department of Applied Mathematics, Beijing University of Technology, Beijing, 100124, 100 Pingleyuan, Chaoyang District

来源：

Journal of the Operations Research Society of China | 2013年 / 1卷 / 3期

关键词：

Approximation algorithm; Facility location; LP-rounding; Risk-adjusted;

D O I：

10.1007/s40305-013-0020-0

中图分类号：

学科分类号：

摘要：

In this paper, we consider the risk-adjusted two-stage stochastic facility location problem with penalties (RSFLPP). Using the monotonicity and positive homogeneity of the risk measure function, we present an LP-rounding-based 6-approximation algorithm. © 2013 Operations Research Society of China, Periodicals Agency of Shanghai University, and Springer-Verlag Berlin Heidelberg.

引用

页码：339 / 346

页数：7

共 17 条

[1]

Ageev A., Ye Y., Zhang J., Improved combinatorial approximation algorithms for the k-level facility location problem, SIAM J. Discrete Math., 18, pp. 207-217, (2004)

[2]

Byrka J., Aardal K.I., An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM J. Comput., 39, pp. 2212-2213, (2010)

[3]

Charikar M., Khuller S., Mount D.M., Naraasimban G., Algorithms for facility location problems with outliers, Proc. Of SODA, pp. 642-651, (2001)

[4]

Chen X., Chen B., Approximation algorithms for soft-capacitated facility location in capacitated network design, Algorithmica, 53, pp. 263-297, (2007)

[5]

Du D., Lu R., Xu D., A primal-dual approximation algorithm for the facility location problem with submodular penalties, Algorithmica, 63, 1-2, pp. 191-200, (2012)

[6]

Guha S., Khuller S., Greedy strike back: improved facility location algorithms, J. Algorithms, 31, pp. 228-248, (1999)

[7]

Hayrapetyan A., Swamy C., Tardos E., Network design for information networks, Proc. Of SODA, pp. 933-942, (2005)

[8]

Jain K., Mahdian M., Markakis E., Saberi A., Vazirani V.V., Greedy facility location algorithm analyzed using dual fitting with factor-revealing LP, J. ACM, 50, pp. 795-824, (2003)

[9]

Jain K., Vazirani V.V., Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, J. ACM, 48, pp. 274-296, (2001)

[10]

Li S., A 1.488-approximation algorithm for the uncapacitated facility location problem, Proc. Of ICALP, Part II, pp. 77-88, (2011)

← 1 2 →