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

Wei Ding () and Ke Qiu ()
Additional contact information
Wei Ding: Zhejiang University of Water Resources and Electric Power
Ke Qiu: Brock University

Journal of Combinatorial Optimization, 2018, vol. 36, issue 4, No 9, 1262-1298

Abstract: 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 ) .

Keywords: Continuous connected 2-facility; Tree; Edge-splitting; Quadratic time (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0213-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:4:d:10.1007_s10878-017-0213-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0213-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().