Abstract
This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let \(T = (V, E, c, d, \ell , \mu )\) be an undirected rooted tree, where each node \(v \in V\) has a weight \(d(v) \ge 0\) denoting the demand amount of v as well as a weight \(\ell (v) \ge 0\) denoting the cost of opening a facility at v, and each edge \(e \in E\) has a weight \(c(e) \ge 0\) denoting the cost on e as well as is associated with a function \(\mu (e,t) \ge 0\) denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset \(\mathcal {D} \subseteq V\) of clients, and a subset \(\mathcal {F} \subseteq \mathcal {P}(T)\) of continuum points admitting facilities where \(\mathcal {P}(T)\) is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points \(x_1\) and \(x_2\) in \(\mathcal {F}\), the total cost involved by CC2FLP includes three parts: the cost of opening two facilities at \(x_1\) and \(x_2\), K times the cost of connecting \(x_1\) and \(x_2\), and the cost of all the clients in \(\mathcal {D}\) connecting to some facility. The objective is to open two facilities at a pair of continuum points in \(\mathcal {F}\) to minimize the total cost, for a given input parameter \(K \ge 1\). This paper considers the case of \(\mathcal {D} = V\) and \(\mathcal {F} = \mathcal {P}(T)\). We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM. 45(3), 501–555 (1998)
Bardossy, M.G., Raghavan, S.: Dual-based local search for the connected facility location and related problems. INFORMS J. Comput. 22(4), 584–602 (2010)
Ding, W., Xue, G.: A linear time algorithm for computing a most reliable source on a tree network with faulty nodes. Theor. Comput. Sci. 412(3), 225–232 (2011)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Eisenbrand, F., Grandoni, F., Rothvoß, T., Schäfer, G.: Connected facility location via random facility sampling and core detouring. J. Comput. Syst. Sci. 76(8), 709–726 (2010)
Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proceedings of 33rd STOC, pp. 389–398 (2001)
Gupta, A., Kumar, A., Roughgarden, T.: Simpler and better approximation algorithms for network design. In: Proceedings of 35th STOC, pp. 365–372 (2003)
Gupta, A., Srinivasan, A., Tardos, É.: Cost-sharing mechanisms for network design. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol. 3122, pp. 139–150. Springer, Heidelberg (2004)
Hasan, M.K., Jung, H., Chwa, K.Y.: Approximation algorithms for connected facility location problems. J. Combinatirial Optim. 16, 155–172 (2008)
Jung, H., Hasan, M.K., Chwa, K.-Y.: Improved primal-dual approximation algorithm for the connected facility location problem. In: Yang, B., Du, D.-Z., Wang, C.A. (eds.) COCOA 2008. LNCS, vol. 5165, pp. 265–277. Springer, Heidelberg (2008)
Karger, D.R., Minkoff, M.: Building Steiner trees with incomplete global knowledge. In: Proceedings of 41st FOCS, pp. 613–623 (2000)
Lee, Y., Chiu, S.Y., Ryan, J.: A branch and cut algorithm for a Steiner tree-star problem. INFORMS J. Comput. 8(3), 194–201 (1996)
Ljubić, I.: A hybrid VNS for connected facility location. In: Bartz-Beielstein, T., Blesa Aguilera, M.J., Blum, C., Naujoks, B., Roli, A., Rudolph, G., Sampels, M. (eds.) HCI/ICCV 2007. LNCS, vol. 4771, pp. 157–169. Springer, Heidelberg (2007)
Ravi, R., Sinha, A.: Approximation algorithms for problems combining facility location and network design. Oper. Res. 54(1), 73–81 (2006)
Swamy, C., Kumar, A.: Primal-dual algorithms for connected facility location problems. Algorithmica 40(4), 245–269 (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Ding, W., Qiu, K. (2016). A Quadratic Time Exact Algorithm for Continuous Connected 2-Facility Location Problem in Trees (Extended Abstract). In: Chan, TH., Li, M., Wang, L. (eds) Combinatorial Optimization and Applications. COCOA 2016. Lecture Notes in Computer Science(), vol 10043. Springer, Cham. https://doi.org/10.1007/978-3-319-48749-6_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-48749-6_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-48748-9
Online ISBN: 978-3-319-48749-6
eBook Packages: Computer ScienceComputer Science (R0)