An approximation algorithm for the nth power metric facility location problem with linear penalties
Tóm tắt
We consider the nth power metric facility location problem with linear penalties (M
$$^n$$
FLPLP) in this work, extending both the nth power metric facility location problem (M
$$^n$$
FLP) and the metric facility location problem with linear penalties (MFLPLP). We present an LP-rounding based approximation algorithm to the M
$$^n$$
FLPLP with bi-factor approximation ratio
$$(\gamma _f, \gamma _c)$$
, where
$$\gamma _f$$
and
$$\gamma _c$$
are the ratios corresponding to facility, and connection and penalty costs respectively. Finally we show that the bi-factor curve is close to the lower bound
$$(\gamma _f, 1 + (3^n - 1) e^{-\gamma _f})$$
when the facility factor
$$\gamma _f > 2$$
for the M
$$^2$$
FLPLP.
Tài liệu tham khảo
Hochbaum, D.S.: Heuristics for the fixed cost median problem. Math. Program. 22, 148–162 (1982)
Shmoys, D.B., Tardos, É., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 265–274 (1997)
Byrka, J., Aardal, K.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput. 39, 2212–2231 (2010)
Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1–25 (2003)
Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45–58 (2013)
Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of the 9th International Integer Programming and Combinatorial Optimization Conference, pp. 240–257 (2002)
Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM. 50, 95–824 (2003)
Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 731–740 (2002)
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, 74–296 (2001)
Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36, 11–432 (2006)
Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: Proceeding of the 40th Annual Symposium on Foundations of Computer Science, pp. 378–388 (1999)
Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms 31, 28–248 (1999)
Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. J. Algorithms 37, 46–188 (2000)
Vygen, J.: Approximation algorithms facility location problems (lecture notes). Technical Report 05950-OR, Research Institute for Discrete Mathematics, University of Bonn (2005)
Aardal, K.: Capacitated facility location: separation algorithms and computational experience. Math. Program. 81, 149–175 (1998)
Zhang, J., Chen, B., Ye, Y.: A multiexchange local search algorithm for the capacitated facility location problem. Math. Oper. Res. 30, 89–403 (2005)
Charikar, M., Li, S.: A dependent LP-rounding approach for the \(k\)-median problem. In: Proceeding of the 39th International Colloquium on Automata, Languages and Programming, pp. 94–205 (2012)
Li, Y., Xiu, N.H., Xu, D.C.: An approximation algorithm for the \(k\)-median warehouse-retailer network design problem. Sci. China Math. 56, 2381–2388 (2013)
Zhang, P.: A new approximation algorithm for the \(k\)-facility location problem. Theor. Comput. Sci. 384, 26–135 (2007)
Ageev, A., Ye, Y., Zhang, J.: Improved combinatorial approximation algorithms for the \(k\)-level facility location problem. SIAM J. Discrete Math. 18, 207–217 (2004)
Li, G., Du, D., Xu, D., et al.: A cost-sharing method for the multi-level economic lot-sizing game. Sci. China Inf. Sci. 57, 1–9 (2014)
Wu, C., Du, D., Xu, D.: Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach. Theor. Comput. Sci. 562, 213–226 (2015)
Fernandes, C.G., Meira, L.A.A., Miyazawa, F.K., Pedrosa, L.L.C.: A systematic approach to bound factor-revealing lps and its application to the metric and squared metric facility location problems. Math. Program. 153, 655–685 (2015)
Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 642–651 (2001)
Xu, G., Xu, J.: An lp rounding algorithm for approximating uncapacitated facility location problem with penalties. Inf. Process. Lett. 94, 19–123 (2005)
Xu, G., Xu, J.: An improved approximation algorithm for uncapacitated facility location problem with penalties. J. Comb. Optim. 17, 24–436 (2009)
Geunes, J., Levi, R., Romeijn, H.E., Shmoys, D.B.: Approximation algorithms for supply chain planning and logistics problems with market choice. Math. Program. 130, 5–106 (2011)
Li, Y., Du, D., Xiu, N., Xu, D.: Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica. 73, 460–482 (2015)