IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v36y2018i4d10.1007_s10878-017-0213-2.html
   My bibliography  Save this article

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

Author

Listed:
  • Wei Ding

    (Zhejiang University of Water Resources and Electric Power)

  • Ke Qiu

    (Brock University)

Abstract

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let $$T = (V, E, c, d, \ell , \mu )$$ T = ( V , E , c , d , ℓ , μ ) be an undirected rooted tree, where each node $$v \in V$$ v ∈ V has a weight $$d(v) \ge 0$$ d ( v ) ≥ 0 denoting the demand amount of v as well as a weight $$\ell (v) \ge 0$$ ℓ ( v ) ≥ 0 denoting the cost of opening a facility at v, and each edge $$e \in E$$ e ∈ E has a weight $$c(e) \ge 0$$ c ( e ) ≥ 0 denoting the cost on e and is associated with a function $$\mu (e,t) \ge 0$$ μ ( e , t ) ≥ 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$$ D ⊆ V of clients, and a subset $$\mathcal {F} \subseteq \mathcal {P}(T)$$ F ⊆ P ( T ) of continuum points admitting facilities where $$\mathcal {P}(T)$$ 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$$ x 1 and $$x_2$$ x 2 in $$\mathcal {F}$$ F , the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at $$x_1$$ x 1 and $$x_2$$ x 2 , K times the cost of connecting $$x_1$$ x 1 and $$x_2$$ x 2 , and the cost of all the clients in $$\mathcal {D}$$ D connecting to some facility. The objective is to open two facilities at a pair of continuum points in $$\mathcal {F}$$ F to minimize the total cost, for a given input parameter $$K \ge 1$$ K ≥ 1 . This paper focuses on the case of $$\mathcal {D} = V$$ D = V and $$\mathcal {F} = \mathcal {P}(T)$$ F = 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 that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of $$\mathcal {D} \subseteq V$$ D ⊆ V and $$\mathcal {F} \subseteq \mathcal {P}(T)$$ F ⊆ P ( T ) .

Suggested Citation

  • Wei Ding & Ke Qiu, 2018. "A quadratic time exact algorithm for continuous connected 2-facility location problem in trees," Journal of Combinatorial Optimization, Springer, vol. 36(4), pages 1262-1298, November.
  • Handle: RePEc:spr:jcomop:v:36:y:2018:i:4:d:10.1007_s10878-017-0213-2
    DOI: 10.1007/s10878-017-0213-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-017-0213-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10878-017-0213-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. S. S. Ting, 1984. "A Linear-Time Algorithm for Maxisum Facility Location on Tree Networks," Transportation Science, INFORMS, vol. 18(1), pages 76-84, February.
    2. Schröer, Sebastian & Straubhaar, Thomas, 2007. "Demographische Entwicklung: Problem oder Phantom?," HWWI Policy Papers 1-1, Hamburg Institute of International Economics (HWWI).
    3. Rainer Burkard & Jafar Fathali, 2007. "A polynomial method for the pos/neg weighted 3-median problem on a tree," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 65(2), pages 229-238, April.
    4. Becker, Ronald I. & Lari, Isabella & Scozzari, Andrea, 2007. "Algorithms for central-median paths with bounded length on trees," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1208-1220, June.
    5. Youngho Lee & Steve Y. Chiu & Jennifer Ryan, 1996. "A Branch and Cut Algorithm for a Steiner Tree-Star Problem," INFORMS Journal on Computing, INFORMS, vol. 8(3), pages 194-201, August.
    6. Jui-Chung Allen Li, 2007. "The Kids Are OK Divorce and Children's Behavior Problems," Working Papers WR-489, RAND Corporation.
    7. Wei Ding & Yu Zhou & Guangting Chen & Hongfa Wang & Guangming Wang, 2013. "On the 2-MRS Problem in a Tree with Unreliable Edges," Journal of Applied Mathematics, Hindawi, vol. 2013, pages 1-11, November.
    8. Richard L. Church & Robert S. Garfinkel, 1978. "Locating an Obnoxious Facility on a Network," Transportation Science, INFORMS, vol. 12(2), pages 107-118, May.
    9. Igor Averbakh & Oded Berman, 2000. "Minmax Regret Median Location on a Network Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 104-110, May.
    10. ., 2007. "Problems of Utility Privatization," Chapters, in: Paul Cook & Sarah Mosedale (ed.), Regulation, Markets and Poverty, chapter 8, Edward Elgar Publishing.
    11. George L. Vairaktarakis & Panagiotis Kouvelis, 1999. "Incorporation dynamic aspects and uncertainty in 1‐median location problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(2), pages 147-168, March.
    12. ., 2007. "Anti-dumping action - problems arising," Chapters, in: Anti-Dumping and Countervailing Action, chapter 5, Edward Elgar Publishing.
    13. Averbakh, Igor & Berman, Oded, 2000. "Algorithms for the robust 1-center problem on a tree," European Journal of Operational Research, Elsevier, vol. 123(2), pages 292-302, June.
    14. Rainer Burkard & Helidon Dollani, 2002. "A Note on the Robust 1-Center Problem on Trees," Annals of Operations Research, Springer, vol. 110(1), pages 69-82, February.
    15. ., 2007. "Subsidies and countervailing action - problems arising," Chapters, in: Anti-Dumping and Countervailing Action, chapter 7, Edward Elgar Publishing.
    16. Arie Tamir & Eitan Zemel, 1982. "Locating Centers on a Tree with Discontinuous Supply and Demand Regions," Mathematics of Operations Research, INFORMS, vol. 7(2), pages 183-197, May.
    17. Mohammad Khairul Hasan & Hyunwoo Jung & Kyung-Yong Chwa, 2008. "Approximation algorithms for connected facility location problems," Journal of Combinatorial Optimization, Springer, vol. 16(2), pages 155-172, August.
    18. Jui-Chung Allen Li, 2007. "The Kids Are OK Divorce and Children's Behavior Problems," Working Papers 489, RAND Corporation.
    19. Yu Zhou & Wei Ding & Guangming Wang & Guangting Chen, 2015. "An Edge-Turbulence Algorithm for the 2-MRS Problem on Trees with Unreliable Edges," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 32(01), pages 1-17.
    20. R. Ravi & Amitabh Sinha, 2006. "Approximation Algorithms for Problems Combining Facility Location and Network Design," Operations Research, INFORMS, vol. 54(1), pages 73-81, February.
    21. Burkard, R. E. & Dollani, Helidon, 2003. "Center problems with pos/neg weights on trees," European Journal of Operational Research, Elsevier, vol. 145(3), pages 483-495, March.
    22. Dickson, D. C. M., 2007. "Some Finite Time Ruin Problems," Annals of Actuarial Science, Cambridge University Press, vol. 2(2), pages 217-232, September.
    23. ., 2007. "A Statement of the Problem," Chapters, in: The Causes, Costs and Compensations of Inflation, chapter 1, Edward Elgar Publishing.
    24. A. J. Goldman, 1971. "Optimal Center Location in Simple Networks," Transportation Science, INFORMS, vol. 5(2), pages 212-221, May.
    25. G. Y. Handler, 1973. "Minimax Location of a Facility in an Undirected Tree Graph," Transportation Science, INFORMS, vol. 7(3), pages 287-293, August.
    26. M. Gisela Bardossy & S. Raghavan, 2010. "Dual-Based Local Search for the Connected Facility Location and Related Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 584-602, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Trung Kien Nguyen & Nguyen Thanh Hung & Huong Nguyen-Thu, 2020. "A linear time algorithm for the p-maxian problem on trees with distance constraint," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 1030-1043, November.
    2. Esmaeil Afrashteh & Behrooz Alizadeh & Fahimeh Baroughi, 2020. "Optimal approaches for upgrading selective obnoxious p-median location problems on tree networks," Annals of Operations Research, Springer, vol. 289(2), pages 153-172, June.
    3. Mehdi Zaferanieh & Jafar Fathali, 2012. "Finding a core of a tree with pos/neg weight," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 76(2), pages 147-160, October.
    4. Rainer E. Burkard & Johannes Hatzl, 2010. "Median problems with positive and negative weights on cycles and cacti," Journal of Combinatorial Optimization, Springer, vol. 20(1), pages 27-46, July.
    5. Rainer Burkard & Jafar Fathali, 2007. "A polynomial method for the pos/neg weighted 3-median problem on a tree," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 65(2), pages 229-238, April.
    6. Vatsa, Amit Kumar & Jayaswal, Sachin, 2021. "Capacitated multi-period maximal covering location problem with server uncertainty," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1107-1126.
    7. Conde, Eduardo, 2007. "Minmax regret location-allocation problem on a network under uncertainty," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1025-1039, June.
    8. Liying Kang & Yukun Cheng, 2010. "The p-maxian problem on block graphs," Journal of Combinatorial Optimization, Springer, vol. 20(2), pages 131-141, August.
    9. Balakrishnan, K. & Changat, M. & Mulder, H.M. & Subhamathi, A.R., 2011. "Consensus Strategies for Signed Profiles on Graphs," Econometric Institute Research Papers EI2011-34, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    10. Chunsong Bai & Jun Du, 2024. "The Constrained 2-Maxian Problem on Cycles," Mathematics, MDPI, vol. 12(6), pages 1-9, March.
    11. Vatsa, Amit Kumar & Jayaswal, Sachin, 2015. "A New Formulation and Benders' Decomposition for Multi-period facility Location Problem with Server Uncertainty," IIMA Working Papers WP2015-02-07, Indian Institute of Management Ahmedabad, Research and Publication Department.
    12. Mulder, H.M. & Pelsmajer, M.J. & Reid, K.B., 2006. "Generalized centrality in trees," Econometric Institute Research Papers EI 2006-16, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    13. Wang, Haitao, 2014. "Minmax regret 1-facility location on uncertain path networks," European Journal of Operational Research, Elsevier, vol. 239(3), pages 636-643.
    14. Vatsa, Amit Kumar & Jayaswal, Sachin, 2016. "A new formulation and Benders decomposition for the multi-period maximal covering facility location problem with server uncertainty," European Journal of Operational Research, Elsevier, vol. 251(2), pages 404-418.
    15. Igor Averbakh & Oded Berman, 2000. "Minmax Regret Median Location on a Network Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 104-110, May.
    16. Welch, S. B. & Salhi, S., 1997. "The obnoxious p facility network location problem with facility interaction," European Journal of Operational Research, Elsevier, vol. 102(2), pages 302-319, October.
    17. Contreras, Ivan & Fernández, Elena, 2012. "General network design: A unified view of combined location and network design problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 680-697.
    18. Van Huy Pham & Nguyen Chi Tam, 2019. "A combinatorial algorithm for the ordered 1-median problem on cactus graphs," OPSEARCH, Springer;Operational Research Society of India, vol. 56(3), pages 780-789, September.
    19. Berman, Oded & Wang, Jiamin, 2011. "The minmax regret gradual covering location problem on a network with incomplete information of demand weights," European Journal of Operational Research, Elsevier, vol. 208(3), pages 233-238, February.
    20. Batta, Rajan & Lejeune, Miguel & Prasad, Srinivas, 2014. "Public facility location using dispersion, population, and equity criteria," European Journal of Operational Research, Elsevier, vol. 234(3), pages 819-829.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:36:y:2018:i:4:d:10.1007_s10878-017-0213-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.