An approximation algorithm for the \(k\)-level uncapacitated facility location problem with penalties. (English) Zbl 1188.68355
Sarbazi-Azad, Hamid (ed.) et al., Advances in computer science and engineering. 13th international CSI computer conference, CSICC 2008, Kish Island, Iran, March 9–11, 2008. Revised selected papers. Berlin: Springer (ISBN 978-3-540-89984-6/pbk; 978-3-540-89985-3/ebook). Communications in Computer and Information Science 6, 41-49 (2008).
Summary: The \(k\)-level Uncapacitated Facility Location (UFL) problem is a generalization of the UFL and the \(k\)-median problems. A significant shortcoming of the classical UFL problem is that often a few very distant customers, known as outliers, can leave an undesirable effect on the final solution. This deficiency is considered in a new variant called UFL with outliers, in which, in contrast to the other problems that need all of the customers to be serviced, there is no need to service the entire set of customers. UFL With Penalties (UFLWP) is a variant of the UFL with outliers problem in which we will decide on whether to provide service for each customer and pay the connection cost, or to reject it and pay the penalty. In this paper we will propose a new 4-approximation algorithm for the UFLWP which is the first algorithm for this kind of problem.
For the entire collection see [Zbl 1154.68025].
For the entire collection see [Zbl 1154.68025].
MSC:
| 68W25 | Approximation algorithms |
Keywords:
facility location; uncapacitated facility location; \(k\)-level facility location; facility location with outliersReferences:
| [1] | Sahin, G., Sural, H.: A review of hierarchical facility location models. J. Computers & Operations Research 34(8), 2310–2331 (2007) · Zbl 1144.90440 · doi:10.1016/j.cor.2005.09.005 |
| [2] | Arya, V., Garg, N., Khandekar, R., Munagala, K., Pandit, V.: Local search heuristic for -median and facility location problems. In: Proceedings of the Thirty-Third Annual ACM Symposium on theory of Computing (STOC 2001), Hersonissos, Greece, pp. 21–29. ACM Press, New York (2001) · Zbl 1323.90031 · doi:10.1145/380752.380755 |
| [3] | Shmoys, D.: Approximation Algorithms For Facility Location Problems. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol. 1913, pp. 27–32. Springer, Heidelberg (2000) · Zbl 0976.68538 · doi:10.1007/3-540-44436-X_4 |
| [4] | Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795–824 (2003) · Zbl 1325.90060 · doi:10.1145/950620.950621 |
| [5] | Xu, G., Xu, J.: An LP rounding algorithm for approximating uncapacitated facility location problem with penalties. J. Information Processing Letters (94), 119–123 (2005) · Zbl 1177.90257 · doi:10.1016/j.ipl.2005.01.005 |
| [6] | Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1–10 (1998) · Zbl 0922.90100 |
| [7] | Xu, D., Du, D.: The -level facility location game. J. Operations Research Letters 34(4), 421–426 (2006) · Zbl 1133.90365 · doi:10.1016/j.orl.2005.06.002 |
| [8] | Aardal, K., Chudak, F.A., Shmoys, D.B.: A 3-approximation algorithm for the k-level uncapacitated facility location problem. J. Information Processing Letters 72(5-6), 161–167 (1999) · Zbl 0994.90090 · doi:10.1016/S0020-0190(99)00144-1 |
| [9] | Jain, K., Vazirani, V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM (48), 274–296 (2001) · Zbl 1138.90417 |
| [10] | Zhang, P.: A new approximation algorithm for the k-facility Location Problem. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol. 3959, pp. 217–230. Springer, Heidelberg (2006) · Zbl 1178.90222 · doi:10.1007/11750321_21 |
| [11] | Charikar, M., Khuller, S., Mount, D., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of Symposium on Discrete Algorithms, pp. 642–651 (2001) · Zbl 1012.90026 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
