Dual-Based Local Search for the Connected Facility Location and Related Problems

References

• Balakrishnan A., Magnanti T. L., Wong R. T. A dual-ascent procedure for large-scale uncapacitated network design. Oper. Res. (1989) 37(5):716–740Link, Google Scholar
• Chu C.-H., Premkumar G., Chou H. Digital data networks design using genetic algorithms. Eur. J. Oper. Res. (2000) 127(1):140–158Crossref, Google Scholar
• Eisenbrand F., Grandoni F., Rothvoß T., Schäfer G. Approximating connected facility location problems via random facility sampling and core detouring. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (2008) (Society Industrial and Applied Mathematics, Philadelphia) 1174–1183Google Scholar
• Gupta A., Kumar A., Roughgarden T. Simpler and better approximation algorithms for network design. Proc. 35th Annual ACM Sympos. Theory Comput. (2003) (ACM, New York) 365–372Crossref, Google Scholar
• Gupta A., Kleinberg J., Kumar A., Rastogi R., Yener B. Provisioning a virtual private network: A network design problem for multicommodity flow. Proc. 33rd Annual ACM Sympos. Theory Comput. (2001) (ACM, New York) 389–398Crossref, Google Scholar
• Havet F., Wennink M. The push tree problem. Networks (2004) 44(4):281–291Crossref, Google Scholar
• Jung H., Hasan M. K., Chwa K. Y., Yang B., Du D.-Z., Wang C. A. Improved primal-dual approximation algorithm for the connected facility location problem. Combinatorial Optimization and Applications (2008) 5165(Springer, Berlin) 265–277Lecture Notes in Computer ScienceCrossref, Google Scholar
• Karger D. R., Minkoff M. Building Steiner trees with incomplete global knowledge. Proc. 41st Annual IEEE Sympos. Foundations Comput. Sci. (2000) (IEEE Computer Society, Washington, DC) 613–623Crossref, Google Scholar
• Khuller S., Zhu A. The general Steiner tree-star problem. Inform. Processing Lett. (2002) 84(4):215–220Crossref, Google Scholar
• Krick C., Räcke H., Westermann M. Approximation algorithms for data management in networks. Theory Comput. Systems (2003) 36(5):497–519Crossref, Google Scholar
• Lee Y., Chiu S. Y., Ryan J. A branch and cut algorithm for a Steiner tree-star problem. INFORMS J. Comput. (1996) 8(3):194–201Link, Google Scholar
• Lee Y., Lu L., Qiu Y., Glover F. Strong formulations and cutting planes for designing digital data service networks. Telecommunication Systems (1993) 2(1):261–274Crossref, Google Scholar
• Ljubić I., Bartz-Beielstein T., Aguilera M. J. B., Blum C., Naujoks B., Roli A., Rudolph G., Sampels M. A hybrid VNS for connected facility location. Hybrid Metaheuristics (2007) 4771(Springer, Berlin) 157–169Lecture Notes in Computer ScienceCrossref, Google Scholar
• Ljubić I. Private communication (February 20). (2009) Google Scholar
• Nuggehalli P., Srinivasan V., Chiasserini C. F. Energy-efficient caching strategies in ad hoc wireless networks. Proc. 4th ACM Internat. Sympos. Mobile Ad Hoc Networking Comput. (2003) (ACM, New York) 25–34Crossref, Google Scholar
• Raghavan S. Formulations and algorithms for network design problems with connectivity requirements. (1995) . Ph.D. thesis, Massachusetts Institute of Technology, CambridgeGoogle Scholar
• Salman F. S., Cheriyan J., Ravi R., Subramanian S. Buy-at-bulk network design: Approximating the single-sink edge installation problem. Proc. 8th Annual ACM-SIAM Sympos. Discrete Algorithms (1997) (Society for Industrial and Applied Mathematics, Philadelphia) 619–628Google Scholar
• Shmoys D. B., Tardos É., Aardal K. Approximation algorithms for facility location problems. Proc. 29th Annual ACM Sympos. Theory Comput. (1997) (ACM, New York) 265–274Google Scholar
• Swamy C., Kumar A. Primal–dual algorithms for connected facility location problems. Algorithmica (2004) 40(4):245–269Crossref, Google Scholar
• Tomazic A., Ljubić I. A GRASP Algorithm for the connected facility location problem. 2008 Internat. Sympos. Appl. Internet (2008) 257–260Crossref, Google Scholar
• Wong R. T. A dual ascent approach for Steiner tree problems on a directed graph. Math. Programming (1984) 28(3):271–287Crossref, Google Scholar
• Xu J., Chiu S. Y., Glover F. Probabilistic tabu search for telecommunications network design. J. Combin. Optim. (1996a) 1:69–94Google Scholar
• Xu J., Chiu S. Y., Glover F. Using tabu search to solve the Steiner tree-star problem in telecommunications network design. Telecommunication Systems (1996b) 6(1):117–125Crossref, Google Scholar