Algorithmic approaches for network design with facility location: A survey

[1] Z. Abrams, A. Meyerson, K. Munagala, and S. Plotkin, The integrality gap of capacitated facility location, Technical Report CMU-CS-02-199, Carnegie Mellon University, (2002).

[2] A. Aggarwal, A. Louis, M. Bansal, N. Garg, N. Gupta, S. Gupta, and S. Jain, A 3-approximation algorithm for the facility location problem with uniform capacities, Mathematical Programming, 141 (2013).

[3] S. Ahmadian and C. Swamy, Improved approximation guarantees for lower-bounded facility location, Approximation and Online Algorithms, (2012), pp. 257–271.

[4] H.-C. An, M. Singh, and O. Svensson, LP-based algorithms for capacitated facility location, In proceedings of FOCS 2014, (2014), pp. 256–265.

[5] M. Andrews, Hardness of buy-at-bulk network design, Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, (2004), pp. 115–124.

[6] A. Arulselvan, M. Rezapour, and W. A. Welz, Exact approaches for designing multifacility buy-at-bulk networks, INFORMS Journal on Computing, 29 (2017), pp. 597–611.

[7] B. Awerbuch and Y. Azar, Buy-at-bulk network design, Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on, (1997), pp. 542–547.

[8] M. Bansal, N. Garg, and N. Gupta, A 5-approximation for capacitated facility location, In proceedings of ESA 2012, (2012), pp. 133–144.

[9] M. G. Bardossy and S. Raghavan, Dual-based local search for the connected facility location and related problems, INFORMS Journal on Computing, 22 (2010), pp. 584–602.

[10] Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, (1996), pp. 184–193.

[11] , On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, (1998), pp. 161–168.

[12] J. F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numerische mathematik, 4 (1962), pp. 238–252.

[13] M. Bern and P. Plassmann, The steiner problem with edge lengths 1 and 2, Information Processing Letters, 32 (1989), pp. 171–176.

[14] A. Bley, S. M. Hashemi, and M. Rezapour, Approximation algorithms for a combined facility location buy-at-bulk network design problem, Theory and Applications of Models of Computation (TAMC), Lecture Notes in Computer Science Vol. 7876, (2013), pp. 72–83.

[15] , Ip modeling of the survivable hop constrained connected facility location problem, Electronic Notes in Discrete Mathematics, 41 (2013), pp. 463–470.

[16] A. Bley and M. Rezapour, Combinatorial approximation algorithms for buy-at-bulk connected facility location problems, Discrete Applied Mathematics, 213 (2016), pp. 34–46.

[17] Q. Botton, B. Fortz, L. Gouveia, and M. Poss, Benders decomposition for the hop-constrained survivable network design problem, INFORMS journal on computing, 25 (2013), pp. 13–26.

[18] J. Byrka and K. Aardal, An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM Journal on Computing, 39 (2010), pp. 2212–2231.

[19] J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanita`, An improved lp-based approximation for steiner tree, Proceedings of the 42nd ACM symposium on Theory of computing, (2010), pp. 583–592.

[20] M. Charikar and S. Guha, Improved combinatorial algorithms for the facility location and k-median problems, Foundations of Computer Science, 1999. 40th Annual Symposium on, (1999), pp. 378–388.

[21] M. Charikar and A. Karagiozova, On non-uniform multicommodity buy-at-bulk network design, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, (2005), pp. 176–182.

[22] C. Chekuri, M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour, Approximation algorithms for nonuniform buy-at-bulk network design, SIAM Journal on Computing, 39 (2010), pp. 1772–1798.

[23] C. Chekuri, S. Khanna, and J. S. Naor, A deterministic algorithm for the cost-distance problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, (2001), pp. 232–233.

[24] M. Chleb´ık and J. Chleb´ıkova´, The steiner tree problem on graphs: Inapproximability results, Theoretical Computer Science, 406 (2008), pp. 207–214.

[25] F. A. Chudak and D. B. Shmoys, Improved approximation algorithms for the uncapacitated facility location problem, SIAM Journal on Computing, 33 (2003), pp. 1–25.

[26] F. A. Chudak and D. P. Williamson, Improved approximation algorithms for capacitated facility location problems, Mathematical programming, 102 (2005).

[27] J. Chuzhoy, A. Gupta, J. S. Naor, and A. Sinha, On the approximability of some network design problems, ACM Transactions on Algorithms (TALG), 4 (2008), p. 23.

[28] V. Chvatal, A greedy heuristic for the set-covering problem, Mathematics of operations research, 4 (1979), pp. 233–235.

[29] G. B. Dantzig and P. Wolfe, Decomposition principle for linear programs, Operations research, 8 (1960), pp. 101–111.

[30] F. Eisenbrand, F. Grandoni, T. Rothvoß, and G. Schafer ¨ , Connected facility location via random facility sampling and core detouring, Journal of Computer and System Sciences, 76 (2010), pp. 709–726.

[31] J. Fakcharoenphol, S. Rao, and K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, (2003), pp. 448–455.

[32] L. Fleischer, K. Jain, and D. P. Williamson, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems, Journal of Computer and System Sciences, 72 (2006), pp. 838–867.

[33] Z. Friggstad, M. Rezapour, and M. R. Salavatipour, Approximating connected facility location with lower and upper bounds via lp rounding, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), (2016).

[34] Z. Friggstad, M. Rezapour, M. R. Salavatipour, and J. A. Soto, Lp-based approximation algorithms for facility location in buy-at-bulk network design, Algorithmica, 81 (2019), pp. 1075–1095.

[35] M. Garey and D. Johnson, Computers and intractability: a guide to the theory of np-completeness, WH Freeman & Co., San Francisco, (1979).

[36] N. Garg, R. Khandekar, G. Konjevod, R. Ravi, F. S. Salman, and A. Sinha, On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem, Integer Programming and Combinatorial Optimization, (2001), pp. 170–184.

[37] M. X. Goemans, A. V. Goldberg, S. A. Plotkin, D. B. Shmoys, E. Tardos, and D. P. Williamson, Improved approximation algorithms for network design problems., SODA, 94 (1994), pp. 223–232.

[38] S. Gollowitzer and I. Ljubic´, Mip models for connected facility location: A theoretical and computational study, Computers & Operations Research, 38 (2011), pp. 435–449.

[39] F. Grandoni and T. Rothvoß, Network design via core detouring for problems without a core, Automata, Languages and Programming, (2010), pp. 490–502.

[40] , Approximation algorithms for single and multi-commodity connected facility location, Integer Programming and Combinatoral Optimization, (2011), pp. 248–260.

[41] S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms, Journal of algorithms, 31 (1999), pp. 228–248.

[42] S. Guha, A. Meyerson, and K. Munagala, Hierarchical placement and network design problems, Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, (2000), pp. 603–612.

[43] , A constant factor approximation for the single sink edge installation problems, Proceedings of the thirtythird annual ACM symposium on Theory of computing, (2001), pp. 383–388.

[44] , A constant factor approximation for the single sink edge installation problem, SIAM Journal on Computing, 38 (2009), pp. 2426–2442.

[45] A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener, Provisioning a virtual private network: a network design problem for multicommodity flow, Proceedings of the thirty-third annual ACM symposium on Theory of computing, (2001), pp. 389–398.

[46] A. Gupta, A. Kumar, and T. Roughgarden, Simpler and better approximation algorithms for network design, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, (2003), pp. 365–372.

[47] N. Gupta, S. Grover, and R. Dabas, Respecting lower bounds in uniform lower and upper bounded facility location problem, International Computing and Combinatorics Conference, (2021), pp. 463–475.

[48] M. K. Hasan, H. Jung, and K.-Y. Chwa, Approximation algorithms for connected facility location problems, Journal of Combinatorial Optimization, 16 (2008), pp. 155–172.

[49] S. M. Hashemi, A. Moradi, and M. Rezapour, An aco algorithm to design umts access network using divided and conquer technique, Engineering Applications of Artificial Intelligence, 21 (2008), pp. 931–940.

[50] S. M. Hashemi, M. Rezapour, and A. Moradi, An effective hybrid pso-based algorithm for planning umts terrestrial access networks, Engineering Optimization, 42 (2010), pp. 241–251.

[51] D. S. Hochbaum, Heuristics for the fixed cost median problem, Mathematical programming, 22 (1982), pp. 148–162.

[52] J. Hromkovic, Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics, Springer-Verlag, (2010).

 [53] D. Huygens, M. Labbe, A. R. Mahjoub, and P. Pesneau ´ , The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut, Networks, 49 (2007), pp. 116–133.

[54] K. Jain, A factor 2 approximation algorithm for the generalized steiner network problem, Combinatorica, 21 (2001), pp. 39–60.

[55] K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing lp, Journal of the ACM (JACM), 50 (2003), pp. 795–824.

[56] K. Jain, M. Mahdian, and A. Saberi, A new greedy approach for facility location problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, (2002), pp. 731–740.

[57] K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation, Journal of the ACM (JACM), 48 (2001), pp. 274–296.

[58] R. Jothi and B. Raghavachari, Improved approximation algorithms for the single-sink buy-at-bulk network design problems, Algorithm Theory-SWAT 2004, (2004), pp. 336–348.

[59] H. Jung, M. K. Hasan, and K.-Y. Chwa, A 6.55 factor primal-dual approximation algorithm for the connected facility location problem, Journal of combinatorial optimization, 18 (2009), pp. 258–271.

[60] D. Karget and M. Minkoff, Building steiner trees with incomplete global knowledge, Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, (2000), pp. 613–623.

[61] N. Karmarkar, A new polynomial-time algorithm for linear programming, Proceedings of the sixteenth annual ACM symposium on Theory of computing, (1984), pp. 302–311.

[62] G. Kortsarz and Z. Nutov, Approximating some network design problems with node costs, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, (2009), pp. 231–243.

[63] M. R. Korupolu, C. G. Plaxton, and R. Rajaraman, Analysis of a local search heuristic for facility location problems, Journal of algorithms, 37 (2000), pp. 146–188.

[64] R. Levi, D. B. Shmoys, and C. Swamy, LP-based approximation algorithms for capacitated facility location, Mathematical programming, 131 (2012).

[65] S. Li, A 1.488 approximation algorithm for the uncapacitated facility location problem, Information and Computation, 222 (2013), pp. 45–58.

[66] , On facility location with general lower bounds, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, (2019), pp. 2279–2290.

[67] J.-H. Lin and J. S. Vitter, Approximation algorithms for geometric median problems, Information Processing Letters, 44 (1992), pp. 245–249.

[68] I. Ljubic´, A hybrid vns for connected facility location, Hybrid Metaheuristics, (2007), pp. 157–169.

[69] I. Ljubic, P. Putz, and J.-J. Salazar-Gonz ´ alez ´ , Exact approaches to the single-source network loading problem, Networks, 59 (2012), pp. 89–106.

[70] M. E. Lubbecke and J. Desrosiers ¨ , Selected topics in column generation, Operations Research, 53 (2005), pp. 1007–1023.

[71] M. Mahdian, Y. Ye, and J. Zhang, Approximation algorithms for metric facility location problems, SIAM Journal on Computing, 36 (2006), pp. 411–432.

[72] A. R. Mahjoub, L. Simonetti, and E. Uchoa, Hop-level flow formulation for the survivable network design with hop constraints problem, Networks, 61 (2013), pp. 171–179.

[73] P. Manyem, Constrained spanning, steiner trees and the triangle inequality, Optimization, (2009), pp. 355– 367.

[74] A. Meyerson, K. Munagala, and S. Plotkin, Cost-distance: Two metric network design, Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, (2000), pp. 624–630.

[75] M. Pal, E. Tardos, and T. Wexler, Facility location with nonuniform hard capacities, In proceedings of FOCS 2001, (2001), pp. 329–338.

[76] S. Raghavan and D. Stanojevic´, A note on search by objective relaxation, Telecommunications planning: innovations in pricing, network design and management, (2006), pp. 181–201.

[77] C. Randazzo, H. P. L. Luna, P. Mahey, et al., Benders decomposition for local access network design with two technologies., Discrete Mathematics & Theoretical Computer Science, 4 (2001), pp. 235–246.

[78] R. Ravi and A. Sinha, Approximation algorithms for problems combining facility location and network design, Operations Research, 54 (2006), pp. 73–81.

[79] M. Rezapour, Network design with facility location: Approximation and exact techniques, Ph.D. Thesis, Technische Universit¨at Berlin, (2015).

[80] G. Robins and A. Zelikovsky, Improved steiner tree approximation in graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, (2000), pp. 770–779.

[81] F. S. Salman, R. Ravi, and J. N. Hooker, Solving the capacitated local access network design problem, INFORMS Journal on Computing, 20 (2008), pp. 243–254.

[82] A. Schrijver, Combinatorial optimization: polyhedra and efficiency, Springer, 24 (2003).

[83] D. B. Shmoys, E. Tardos, and K. Aardal ´ , Approximation algorithms for facility location problems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, (1997), pp. 265–274.

[84] M. Sviridenko, An improved approximation algorithm for the metric uncapacitated facility location problem, Integer programming and combinatorial optimization, (2002), pp. 240–257.

[85] Z. Svitkina, Lower-bounded facility location, ACM Transactions on Algorithms (TALG), 6 (2010), p. 69.

[86] C. Swamy and A. Kumar, Primal–dual algorithms for connected facility location problems, Algorithmica, 40 (2004), pp. 245–269.

[87] H. Takahashi and A. Matsuyama, An approximate solution for the steiner problem in graphs, Math. Japonica, 24 (1980), pp. 573–577.

[88] K. Talwar, The single-sink buy-at-bulk lp has constant integrality gap, Integer Programming and Combinatorial Optimization, (2002), pp. 475–486.

[89] A. Tomazic and I. Ljubic´, A grasp algorithm for the connected facility location problem, Applications and the Internet, 2008. SAINT 2008. International Symposium on, (2008), pp. 257–260.

[90] V. V. Vazirani, Approximation algorithms, springer, (2001).

[91] J. Vygen, Approximation algorithms facility location problems, Report No. 05950-OR, Research Institute for Discrete Mathematics, University of Bonn, (2005).

[92] D. P. Williamson, M. X. Goemans, M. Mihail, and V. V. Vazirani, A primal-dual approximation algorithm for generalized steiner network problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, (1993), pp. 708–717.

[93] , A primal-dual approximation algorithm for generalized steiner network problems, Combinatorica, 15 (1995), pp. 435–454.

[94] D. P. Williamson and D. B. Shmoys, The design of approximation algorithms, Cambridge University Press, (2011).

[95] L. A. Wolsey, Integer programming, Wiley New York, 42 (1998).