# The Inverse 1-Median Problem on Tree Networks with Variable Real Edge Lengths

Authors: Longshu Wu; Joonwhoan Lee; Jianhua Zhang; Qin Wang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Location problems exist in the real world and they mainly deal with finding optimal locations for facilities in a network, such as net servers, hospitals, and shopping centers. The inverse location problem is also often met in practice and has been intensively investigated in the literature. As a typical inverse location problem, the inverse 1-median problem on tree networks with variable real edge lengths is discussed in this paper, which is to modify the edge lengths at minimum total cost such that a given vertex becomes a 1-median of the tree network with respect to the new edge lengths. First, this problem is shown to be solvable in linear time with variable nonnegative edge lengths. For the case when negative edge lengths are allowable, the NP-hardness is proved under Hamming distance, and strongly polynomial time algorithms are presented underl1 and l∞ norms, respectively.


---

## Body

## 1. Introduction

Location problems have found important applications in operations research, computer science, and logistics management. Thep-median problem is a typical location problem and has been intensively considered in the literature. The p-median problem on an undirected graph is to locate p  facilities on edges or vertices of the graph such that the sum of the weighted distances of the vertices to the closest facility is minimized. This problem possesses the vertex optimality property which asserts that there exists an optimal solution such that all facilities are located at the vertices of the graph. Kariv and Hakimi [1] showed that the p-median problem is NP-hard even if the graph G is a planar graph of maximum degree 3. Therefore, many investigations are dedicated to special graph classes which allow a more efficient algorithm. In the case of tree networks, the 1-median problem is solvable in linear time by Hua [2] and Goldman [3].However, in an established network, the locations of facilities have already been fixed. The changing environment might make the existing facilities deviate from the median places of the network. Instead of finding optimal locations, the task is to modify parameters at minimum cost such that the prespecified locations become optimal. This arises what we call the inversep-median problem. In recent years, inverse p-median problem found an increasing interest [4–8].Burkard et al. [9] considered inverse p-median problems with variable vertex weights and showed that discrete inverse p-median problems with real weights can be solved in polynomial time, if p is fixed and not an input parameter.Burkard et al. [9, 10] investigated the inverse 1-median problem with variable vertex weights and showed that the problem is solvable by a greedy-type algorithm in O(nlogn) time if the underlying network is a tree or the location problem is defined in the plane (if the distances between the points are measured in the Manhattan or maximum metric) and in O(n2) time on cycles. The inverse Fermat-Weber problem was studied by Burkard et al. [11]. They derived a combinatorial approach which solves the problem in O(nlogn) time for unit cost and under the assumption that the prespecified point that should become a 1-median does not coincide with a given point in the plane. Galavii [12] proposed linear time algorithms for the inverse 1-median problem with variable vertex weights on trees (with nonnegative weights) and on paths (with negative weights while the weights of endpoints are arbitrary). Under weighted Hamming distance, Guan and Zhang [13] presented polynomial time algorithm for the inverse 1-median problem with variable vertex weights on trees. Bonab et al. [14] showed that the inverse p-median problem with variable edge lengths is strongly NP-hard on general graphs and weakly NP-hard on series-parallel graphs. In [14], the authors also presented a polynomial time algorithm for the inverse 2-median problem with positive variable edge lengths on trees and a linear time algorithm for the special case of star graphs. In this paper, we first provide a linear time algorithm to solve the inverse 1-median problem on tree networks with variable nonnegative edge lengths. For the case when negative edge lengths are allowable, we show that this problem is NP-hard under Hamming distance and we propose strongly polynomial time algorithms under l1 and l∞ norms, respectively.The paper is organized as follows. In Section2, we define the inverse 1-median problem on trees with variable edge lengths, then we show some properties of this problem. Based on these properties, a linear time algorithm for variable nonnegative edge lengths is presented; when negative edge lengths are allowable, the NP-hardness of the problem under Hamming distance is proved and the strongly polynomial time algorithms of the problem under l1 and l∞ norms are proposed in Section 3. Some final remarks are given in Section 4.


## 2. Preliminaries

LetT=(V,E) be an undirected tree graph with vertex set V={v1,…,vn} and edge set E with |E|=n-1. The weight of a vertex v∈V is denoted by wv≥0, and the length of each edge e∈E is denoted by le>0. The 1-median problem on trees is to locate a facility on V such that the sum of the weighted distances of the vertices to this facility is minimized.LetC(a):RE→R be a criterion function (having length vectors as argument) such that C(0)=0 and C(a)≤C(b) if a≤b. (For a,b∈RE, a≤b means that ae≤be, for all e∈E.) Suppose that the unique path from s∈V to t∈V is denoted by P(s,t). Let v0 be a specific vertex in V. Denote the adjusted edge length vector by x. Let dx(s,t) denote the length of P(s,t) with respect to x. The lower bound of xe is denoted by l_e≤0 for each e∈E. Readers can refer to [15] for other graph theory terms not defined here. The inverse 1-median problem on tree networks with variable real edge lengths can be formally described as follows:
(1)minC(|l-x|)s.t.∑v∈V∖{v0}wvdx(v0,v)-∑v∈V∖{v¯}wvdx(v¯,v)≤0,∀v¯∈V∖{v0},xe≥l_e,e∈E.If we delete an edgee from T, the tree T will be partitioned into two subtrees, one of which containing the prespecified vertex v0 is denoted by Te′=(Ve′,Ee′), and the other is denoted by Te′′=(Ve′′,Ee′′), where Ve′, Ve′′denote the vertex sets and Ee′, Ee′′ denote the edge sets of Te′, Te′′, respectively. Let Dx(t)=∑v∈V∖{t}wvdx(t,v), and let Be=∑v∈Ve′′wv-∑v∈Ve′wv for each e∈E; then for any v¯∈V∖{v0},
(2)Dx(v0)-Dx(v¯)=∑v∈v∖{v0}wvdx(v0,v)-∑v∈v∖{v¯}wvdx(v¯,v)=∑e∈P(v0,v¯)(∑v∈Ve′′wv-∑v∈Ve′wv)xe=∑e∈P(v0,v¯)Bexe,
and the first constraint of (1) can be changed to
(3)∑e∈P(v0,v¯)Bexe≤0,∀v¯∈V∖{v0}.
So, we can simplify (1) as
(4)minC(|l-x|)s.t.∑e∈P(v0,v¯)Bexe≤0,∀v¯∈V∖{v0},xe≥l_e,e∈E.For anyvr∈V∖{v0}, without loss of generality, suppose the sequence of vertices and edges in P(v0,vr) is v0,e1,v1,e2,v2,…,vr-1,er,vr. We have
(5)∑v∈Vei′′wv≤∑v∈Vei-1′′wv-wvi-1,∑v∈Vei′wv≥∑v∈Vei-1′wv+wvi-1.
Therefore,
(6)∑v∈Vei′′wv-∑v∈Vei′wv≤(∑v∈Vei-1′′wv-wvi-1)-(∑v∈Vei-1′wv+wvi-1)=∑v∈Vei-1′′wv-∑v∈Vei-1′wv-2wvi-1.
Then, for i=1,2,…,r, by (2), we have
(7)Dx(v0)-Dx(vi)=∑e∈P(v0,vi)Bexe=∑j=1iBejxej,Bei-Bei-1=(∑v∈Vei′′wv-∑v∈Vei′wv)-(∑v∈Vei-1′′wv-∑v∈Vei-1′wv)≤((∑v∈Vei-1′′wv-∑v∈Vei-1′wv)-2wvi-1)-(∑v∈Vei-1′′wv-∑v∈Vei-1′wv)=-2wvi-1≤0.
According to (7), we further obtain the following two formulas:
(8)Dx(v0)-Dx(vj)=Dx(v0)-Dx(vi)+∑e∈P(vi,vj)Bele,0≤i<j≤r,(9)Bei-1≥Bei,i=2,…,r.From the above analysis, we have the following.Theorem 1.
If there exists a vertexvt∈V satisfying Dl(v0)-Dl(vt)≤0, then Bet≤0 and Dl(v0)-Dl(v)≤0 for each v∈Vet′′, where et denotes the edge of the path P(v0,vt) incident with vertex vt.Proof.
By contradiction. IfBet>0, then from (9) we have Be>0 for each edge e∈P(v0,vt). By (2), Dl(v0)-Dl(vt)=∑e∈P(v0,vt)Bele>0, which contradicts the fact that Dl(v0)-Dl(vt)≤0. So Bet≤0. As Be≤Bet≤0, for each e∈P(vt,v) and v∈Vet′′, by (8), we can deduce that Dl(v0)-Dl(v)=Dl(v0)-Dl(vt)+∑e∈P(vt,v)Bele≤0. This completes the proof.Based on the above properties, we will present some algorithms of the problem under different norms and analyses their complexities in the next section.


## 3. Algorithms and Complexities

### 3.1. The Problem with Variable Nonnegative Edge Lengths (I1MT-N)

In this section, we consider the following problem:I1MT-N. When l_e=0 for each e∈E, we call (4) Problem I1MT-N, which is the inverse 1-median problem on trees with variable nonnegative edge lengths.Denote the optimal solution of Problem I1MT-N byl*. We present Algorithm 2 to solve this problem. particulary, Algorithm 2 can solve Problem I1MT-N under all kinds of norms only by edge length reduction.Algorithm 2.
Step  1. Let E¯=∅, V¯={v0}.
Step  2. Let E′={e′∣e′=(v,v¯)∈E∖E¯,v∈V∖V¯,v¯∈V¯}. For each e′∈E′,(1)
ifBe′>0, then let le′*=0 and E¯=E¯∪{e′};(2)
ifBe′≤0, then for each e∈{e′}∪Ee′′′, let le*=le and E¯=E¯∪{e′}∪Ee′′′.
Step  3. Let V¯={v∣(v,v¯)=e′∈E′,v¯∈V¯ and Be′>0}. If E¯=E, stop. Otherwise, turn to Step 2.Theorem 3.
Algorithm2 correctly finds the optimal solution l*of Problem I1MT-N in linear time.Proof.
First, we show thatl*obtained by Algorithm 2 is a feasible solution of Problem I1MT-N. It is clear that le*=0 or le*=le; so it satisfies le*≥0 for each e∈E. For each vertex v∈V∖{v0} and  e∈P(v0,v), from Step 2 of Algorithm 2, when Be>0, le*=0; and when le*=le>0, Be≤0. Hence, ∑e∈P(v0,v)Bele*≤0 for each v∈V∖{v0}. Therefore, l* is a feasible solution of Problem I1MT-N.Supposel* is not the optimal solution of Problem I1MT-N and suppose that the optimal solution is l′. Then under l′ there exists at least one edge e¯∈E satisfying one of the following two cases:Case 1 (Be¯>0 and le¯′>0).
Without loss of generality, supposee¯=(vi-1,vi)∈P(v0,vi)=v0,e1,v1,e2,v2,…,vi-1,ei,vi. By (9), Bej≥Be¯>0 for j=1,…,i-1. Notice that le′≥0 for each e∈E. We have ∑j=1iBejlej′>0, which contradicts the feasibility of l′.Case 2 (Be¯≤0 and le¯′≥0,le¯′≠le¯).
We define a new vectorl′′∈RE such that
(10)le′′={le,ife=e¯,le′,otherwise.
From the result of Case 1, we know that when Be>0,  le′′=le′=0. And it is easy to see that le′′≥0 for each e∈E. Then, we have ∑e∈P(v0,v)Bele′′=∑e∈P(v0,v),Be≤0Bele′′≤0 for each vertex v∈V. So l′′is a feasible solution of Problem I1MT-N. But C(|l-l′′|)<C(|l-l′|), a contradiction to the optimality assumption of l′.Therefore, Algorithm2 correctly finds the optimal solution l*of Problem I1MT-N.The main computation of Algorithm2 is to compute Be for each edge e∈E, then to modify the corresponding edge length of  e according to Be from Step 2. Notice that
(11)Be=∑v∈Ve′′wv-∑v∈Ve′wv=2∑v∈Ve′′wv-∑v∈Vwv,
where ∑v∈Vwv is a constant. Let v0 be the root vertex and conduct the breadth-first method to T. We can compute Be iteratively from the edges incident with the leaves at the bottom layer up to v0 in the rooted tree. So Problem I1MT-N can be solved in O(|E|) time by using Algorithm 2.From Algorithm2, we know that for Problem I1MT-N it is not necessary to increase the edge lengths of the tree network. So to solve Problem I1MT-N is equivalent to solving the following program:
(12)minC(l-x)s.t.∑e∈P(v0,v¯)Bexe≤0,∀v¯∈V∖{v0},0≤xe≤le,e∈E.


### 3.2. The Problem with Variable Real Edge Lengths

#### 3.2.1. The Model Underl1 Norm with Variable Real Edge Lengths (I1MT-R-l1)

In this section, we consider the following inverse 1-median problem on trees with variable real edge lengths underl1 norm when edge length increase is forbidden.I1MT-R-l1. When l_e<0 for each e∈E and the criterion function C(a):RE→R is a function such that C(a)=ca, where c is the cost vector and ce>0 is the cost of decreasing le by one unit for each e∈E, we call (4) Problem I1MT-R-l1, which is the inverse 1-median problem on trees with variable real edge lengths under l1 norm.Problem I1MT-R-l1can be formally described as follows:
(13)min∑e∈Ece(le-xe)s.t.∑e∈P(v0,v¯)Bexe≤0,∀v¯∈V∖{v0},l_e≤xe≤le,e∈E.For a pathP(v0,vr)=v0,e1,v1,e2,v2,…,vr-1,er,vr, suppose that Bei-1>0 and Bei≤0, where 2≤i≤r. Denote the optimal solution of Problem I1MT-R-l1 by lopt. We have the following.Theorem 4.
l
e
j
o
p
t
=
l
e
j for j=i,i+1,…,r.Proof.
By (9), clearly Bej>0 for j=1,2,…,i-1 and Bei≤0 for j=i,i+1,…,r. Suppose to the contrary that there exists an edge ek∈P(vi-1,vr) such that  l_ek≤lekopt<lek. Similar to the proof of Case 2 in Theorem 3, we define a new feasible solution l′′ such that lek′′=lek and lej′′=lejopt when j≠k. Then we have ∑e∈P(v0,v)Bele′′≤∑e∈P(v0,v)Beleopt≤0 for each vertex v∈V. But ce(le-le′′)<ce(le-leopt), and therefore c(l-l′′)<c(l-lopt), a contradiction to the fact that lopt is the optimal solution of Problem I1MT-R-l1. This completes the proof.From Theorem4, we only need to determine the optimal adjusted edge lengths leopt with Be>0. We construct the subtree TS=(VS,ES) of T with ES={e∣Be>0,e∈E}, TS=T[ES], and VS=V(TS). Clearly, v0∈VS. Regard TS as a directed tree with the orientation from the root v0 to all leaves (e.g., by conducting the breadth-first method). For each v∈VS, let P(v) denote the path from v0 to v on the tree TS. We can simplify (13) as
(14)min∑e∈ESce(le-xe)s.t.∑e∈P(v)Bexe≤0,∀v∈VS∖{v0},l_e≤xe≤le,∀e∈ES.In [16, 17], the authors considered the shortest path improvement problem, which is how to shorten the lengths of edges with as less cost as possible such that the distances between specified sources and terminals are reduced to the required bounds. It is not difficult to see that (14) is in fact a shortest path improvement problem for tree networks with single source v0 and the required bound 0 under l1 norm. Let θe=Be(le-xe)≥0, be=Be(le-l_e)>0, and pe=ce/Be>0 for each e∈ES. Let rv=∑e∈P(v)Bele>0 for each v∈VS. Equation (14) can be formulated as the following linear program:
(15)min∑e∈ESpeθes.t.∑e∈P(v)θe≥rv,∀v∈VS∖{v0},0≤θe≤be,∀e∈ES.
Equation (15) is a combinatorial linear program and can be solved by a strongly polynomial time algorithm [18]. Moreover, (15) can be solved much faster [16, 17]. In [16], the authors presented a steepest descent-type combinatorial algorithm to solve this problem, which runs in O(|V|2) time. In [17], the authors formulated the dual problem of (15) as a minimum cost flow problem on a two-terminal serial-parallel graph and then gave an algorithm to obtain the primal optimal solution of (15), with the whole procedure running in O(|V|log|V|) time.From the above analysis, we have the following theorem.Theorem 5.
Problem I1MT-R-L1 can be solved in O(|V|log|V|) time.


#### 3.2.2. The Model under Hamming Distance with Variable Real Edge Lengths (I1MT-R-H)

Now we consider the model under Hamming distance. The definition of Hamming distance will be given in this section.I1MT-R-H. When l_e<0 for each e∈E and ce>0 is the cost of decreasing le for each e∈E, we call the following program (16) Problem I1MT-R-H, which is the inverse 1-median problem on trees with variable real edge lengths under Hamming distance:
(16)min∑e∈EceH(xe,le)s.t.∑e∈P(v0,v¯)Bexe≤0,∀v¯∈V∖{v0},l_e≤xe≤le,e∈E,where the Hamming distance H(xe,le) is defined as
(17)H(xe,le)={0,xe=le,1,xe≠le.From a similar discussion in the former Section3.2.1, Problem I1MT-R-H can be formulated as follows:
(18)min∑e∈ESceH(xe,le)s.t.∑e∈P(v)Bexe≤0,∀v∈VS∖{v0},l_e≤xe≤le,∀e∈ES.
Equation (18) is a shortest path improvement problem for tree networks with single source v0 and the required bound 0 under Hamming distance [19]. In [19], the authors proved that even if the network is a chain network, the problem is still NP-hard. So, we have the following.Theorem 6.
Problem I1MT-R-H is NP-hard.


#### 3.2.3. The Model underl∞ Norm with Variable Real Edge Lengths (I1MT-R-l∞)

We consider the model underl∞ norm as follows:I1MT-R-l∞. When l_e<0 for each e∈E and the criterion function C(a):RE→R is a function such that C(a)=||ca||∞, where c is the cost vector, ce>0 is the cost of decreasing le by one unit for each e∈E, and ∥u∥∞=maxe∈E|ue| stands for l∞ norm of vector u, we call (4) Problem I1MT-R-l∞, which is the inverse 1-median problem on trees with variable real edge lengths under l∞ norm.Also from a similar discussion in Section3.2.1, Problem I1MT-R-l∞can be formally described as follows:
(19)minmaxe∈ESce(le-xe)s.t.∑e∈P(v)Bexe≤0,∀v∈VS∖{v0},l_e≤xe≤le,∀e∈ES.
Let te′=Be(xe-l_e), te=Be(le-l_e), he=ce/Be, Ly(P(v))=∑e∈P(v)ye, and U(v)=-∑e∈P(v)Bel_e for each e∈ES and v∈VS∖{v0}. First, we suppose that he=1 for each e∈ES. Equation (19) can be formulated as the following program:
(20)minmaxe∈ES(te-te′)s.t.Lt′(P(v))≤U(v),∀v∈VS∖{v0},0≤te′≤te,∀e∈ES.In [20], the authors presented a strongly polynomial time algorithm to solve this type of problem, which runs in O(|V|3) time. Because the network concerned here is tree network, we now give a simplified procedure to solve (20) which runs in O(|V|2) time.On treeTS, if max{Lt(P(v))-U(v)∣v∈VS∖{v0}}≤0, we need do nothing. Hence, we only consider the case that max{Lt(P(v))-U(v)∣v∈VS∖{v0}}>0. Clearly, the optimal solution t* satisfies max{Lt*(P(v))-U(v)∣v∈VS∖{v0}}=0. Denote θ*=∥t-t*∥∞, then for any edge e∈ES, we have te*=max{te-θ*,0}.As the procedure in [20], first we sort the edges by their lengths in an increasing order. Beginning with the shortest edge, say e′, set te′=te-te′ for each e∈ES, and check if max{Lt′(P(v))-U(v)∣v∈VS∖{v0}}<0. If yes, we know that the lengths are overreduced and θ*<te′. If max{Lt′(P(v))-U(v)∣v∈VS∖{v0}}=0, t*=t′ is the optimal solution. If max{Lt′(P(v))-U(v)∣v∈VS∖{v0}}>0, then  θ*>te′, and in this case we contract the edges e with te′=0 into vertices and repeat the process on the resulted network with respect to t′. Since at least one vertex disappears in each contraction, the procedure has at most |V| iterations. For the time complexity, to find the shortest edge e′ can be completed in O(|E|) time, and in each iteration, the time for checking if max{Lt′(P(v))-U(v)∣v∈VS∖{v0}}<0 is O(|V|). Hence, the complexity of this procedure is O(|V|2). In the following, we assume that θ*<te′, which means that the preliminary procedure is finished while the optimality has not been reached.Because the path between any two vertices on tree network is unique, letQ denotes the set of vertices which does not satisfy the upper bound demand. Let |P| be the number of edges of path P. Let
(21)θ=max{Lt(P(v))-U(v)|P(v)|∣v∈Q},
then θ*=θ is the optimal reduction.Remark 7.
Note that whenhe≠1 for each e∈ES, (20) can be formulated as the following program:
(22)minmaxe∈EShe(te-te′)s.t.Lt′(P(v))≤U(v),∀v∈VS∖{v0},0≤te′≤te,∀e∈ES.In this case, we denoteθ*=∥h(t-t*)∥∞; then for any edge e∈ES, we have te*=max{te-θ*/he,0}. We sort the edges by tehe(e∈ES) in an increasing order to conduct the preliminary procedure to ensure that θ*<te′he′, where e′ is the edge satisfying te′he′=min{tehe∣e∈ES}. Let
(23)θ=max{Lt(P(v))-U(v)∑e∈P(v)1/he∣v∈Q},
then θ*=θ is the optimal reduction. Similar discussions show that the above procedure correctly solves program (22), and its computational complexity is O(|V|2).From the above analysis, we have the following theorem.Theorem 8.
Problem I1MT-R-l∞ can be solved in O(|V|2) time.


## 3.1. The Problem with Variable Nonnegative Edge Lengths (I1MT-N)

In this section, we consider the following problem:I1MT-N. When l_e=0 for each e∈E, we call (4) Problem I1MT-N, which is the inverse 1-median problem on trees with variable nonnegative edge lengths.Denote the optimal solution of Problem I1MT-N byl*. We present Algorithm 2 to solve this problem. particulary, Algorithm 2 can solve Problem I1MT-N under all kinds of norms only by edge length reduction.Algorithm 2.
Step  1. Let E¯=∅, V¯={v0}.
Step  2. Let E′={e′∣e′=(v,v¯)∈E∖E¯,v∈V∖V¯,v¯∈V¯}. For each e′∈E′,(1)
ifBe′>0, then let le′*=0 and E¯=E¯∪{e′};(2)
ifBe′≤0, then for each e∈{e′}∪Ee′′′, let le*=le and E¯=E¯∪{e′}∪Ee′′′.
Step  3. Let V¯={v∣(v,v¯)=e′∈E′,v¯∈V¯ and Be′>0}. If E¯=E, stop. Otherwise, turn to Step 2.Theorem 3.
Algorithm2 correctly finds the optimal solution l*of Problem I1MT-N in linear time.Proof.
First, we show thatl*obtained by Algorithm 2 is a feasible solution of Problem I1MT-N. It is clear that le*=0 or le*=le; so it satisfies le*≥0 for each e∈E. For each vertex v∈V∖{v0} and  e∈P(v0,v), from Step 2 of Algorithm 2, when Be>0, le*=0; and when le*=le>0, Be≤0. Hence, ∑e∈P(v0,v)Bele*≤0 for each v∈V∖{v0}. Therefore, l* is a feasible solution of Problem I1MT-N.Supposel* is not the optimal solution of Problem I1MT-N and suppose that the optimal solution is l′. Then under l′ there exists at least one edge e¯∈E satisfying one of the following two cases:Case 1 (Be¯>0 and le¯′>0).
Without loss of generality, supposee¯=(vi-1,vi)∈P(v0,vi)=v0,e1,v1,e2,v2,…,vi-1,ei,vi. By (9), Bej≥Be¯>0 for j=1,…,i-1. Notice that le′≥0 for each e∈E. We have ∑j=1iBejlej′>0, which contradicts the feasibility of l′.Case 2 (Be¯≤0 and le¯′≥0,le¯′≠le¯).
We define a new vectorl′′∈RE such that
(10)le′′={le,ife=e¯,le′,otherwise.
From the result of Case 1, we know that when Be>0,  le′′=le′=0. And it is easy to see that le′′≥0 for each e∈E. Then, we have ∑e∈P(v0,v)Bele′′=∑e∈P(v0,v),Be≤0Bele′′≤0 for each vertex v∈V. So l′′is a feasible solution of Problem I1MT-N. But C(|l-l′′|)<C(|l-l′|), a contradiction to the optimality assumption of l′.Therefore, Algorithm2 correctly finds the optimal solution l*of Problem I1MT-N.The main computation of Algorithm2 is to compute Be for each edge e∈E, then to modify the corresponding edge length of  e according to Be from Step 2. Notice that
(11)Be=∑v∈Ve′′wv-∑v∈Ve′wv=2∑v∈Ve′′wv-∑v∈Vwv,
where ∑v∈Vwv is a constant. Let v0 be the root vertex and conduct the breadth-first method to T. We can compute Be iteratively from the edges incident with the leaves at the bottom layer up to v0 in the rooted tree. So Problem I1MT-N can be solved in O(|E|) time by using Algorithm 2.From Algorithm2, we know that for Problem I1MT-N it is not necessary to increase the edge lengths of the tree network. So to solve Problem I1MT-N is equivalent to solving the following program:
(12)minC(l-x)s.t.∑e∈P(v0,v¯)Bexe≤0,∀v¯∈V∖{v0},0≤xe≤le,e∈E.


## 3.2. The Problem with Variable Real Edge Lengths

### 3.2.1. The Model Underl1 Norm with Variable Real Edge Lengths (I1MT-R-l1)

In this section, we consider the following inverse 1-median problem on trees with variable real edge lengths underl1 norm when edge length increase is forbidden.I1MT-R-l1. When l_e<0 for each e∈E and the criterion function C(a):RE→R is a function such that C(a)=ca, where c is the cost vector and ce>0 is the cost of decreasing le by one unit for each e∈E, we call (4) Problem I1MT-R-l1, which is the inverse 1-median problem on trees with variable real edge lengths under l1 norm.Problem I1MT-R-l1can be formally described as follows:
(13)min∑e∈Ece(le-xe)s.t.∑e∈P(v0,v¯)Bexe≤0,∀v¯∈V∖{v0},l_e≤xe≤le,e∈E.For a pathP(v0,vr)=v0,e1,v1,e2,v2,…,vr-1,er,vr, suppose that Bei-1>0 and Bei≤0, where 2≤i≤r. Denote the optimal solution of Problem I1MT-R-l1 by lopt. We have the following.Theorem 4.
l
e
j
o
p
t
=
l
e
j for j=i,i+1,…,r.Proof.
By (9), clearly Bej>0 for j=1,2,…,i-1 and Bei≤0 for j=i,i+1,…,r. Suppose to the contrary that there exists an edge ek∈P(vi-1,vr) such that  l_ek≤lekopt<lek. Similar to the proof of Case 2 in Theorem 3, we define a new feasible solution l′′ such that lek′′=lek and lej′′=lejopt when j≠k. Then we have ∑e∈P(v0,v)Bele′′≤∑e∈P(v0,v)Beleopt≤0 for each vertex v∈V. But ce(le-le′′)<ce(le-leopt), and therefore c(l-l′′)<c(l-lopt), a contradiction to the fact that lopt is the optimal solution of Problem I1MT-R-l1. This completes the proof.From Theorem4, we only need to determine the optimal adjusted edge lengths leopt with Be>0. We construct the subtree TS=(VS,ES) of T with ES={e∣Be>0,e∈E}, TS=T[ES], and VS=V(TS). Clearly, v0∈VS. Regard TS as a directed tree with the orientation from the root v0 to all leaves (e.g., by conducting the breadth-first method). For each v∈VS, let P(v) denote the path from v0 to v on the tree TS. We can simplify (13) as
(14)min∑e∈ESce(le-xe)s.t.∑e∈P(v)Bexe≤0,∀v∈VS∖{v0},l_e≤xe≤le,∀e∈ES.In [16, 17], the authors considered the shortest path improvement problem, which is how to shorten the lengths of edges with as less cost as possible such that the distances between specified sources and terminals are reduced to the required bounds. It is not difficult to see that (14) is in fact a shortest path improvement problem for tree networks with single source v0 and the required bound 0 under l1 norm. Let θe=Be(le-xe)≥0, be=Be(le-l_e)>0, and pe=ce/Be>0 for each e∈ES. Let rv=∑e∈P(v)Bele>0 for each v∈VS. Equation (14) can be formulated as the following linear program:
(15)min∑e∈ESpeθes.t.∑e∈P(v)θe≥rv,∀v∈VS∖{v0},0≤θe≤be,∀e∈ES.
Equation (15) is a combinatorial linear program and can be solved by a strongly polynomial time algorithm [18]. Moreover, (15) can be solved much faster [16, 17]. In [16], the authors presented a steepest descent-type combinatorial algorithm to solve this problem, which runs in O(|V|2) time. In [17], the authors formulated the dual problem of (15) as a minimum cost flow problem on a two-terminal serial-parallel graph and then gave an algorithm to obtain the primal optimal solution of (15), with the whole procedure running in O(|V|log|V|) time.From the above analysis, we have the following theorem.Theorem 5.
Problem I1MT-R-L1 can be solved in O(|V|log|V|) time.


### 3.2.2. The Model under Hamming Distance with Variable Real Edge Lengths (I1MT-R-H)

Now we consider the model under Hamming distance. The definition of Hamming distance will be given in this section.I1MT-R-H. When l_e<0 for each e∈E and ce>0 is the cost of decreasing le for each e∈E, we call the following program (16) Problem I1MT-R-H, which is the inverse 1-median problem on trees with variable real edge lengths under Hamming distance:
(16)min∑e∈EceH(xe,le)s.t.∑e∈P(v0,v¯)Bexe≤0,∀v¯∈V∖{v0},l_e≤xe≤le,e∈E,where the Hamming distance H(xe,le) is defined as
(17)H(xe,le)={0,xe=le,1,xe≠le.From a similar discussion in the former Section3.2.1, Problem I1MT-R-H can be formulated as follows:
(18)min∑e∈ESceH(xe,le)s.t.∑e∈P(v)Bexe≤0,∀v∈VS∖{v0},l_e≤xe≤le,∀e∈ES.
Equation (18) is a shortest path improvement problem for tree networks with single source v0 and the required bound 0 under Hamming distance [19]. In [19], the authors proved that even if the network is a chain network, the problem is still NP-hard. So, we have the following.Theorem 6.
Problem I1MT-R-H is NP-hard.


### 3.2.3. The Model underl∞ Norm with Variable Real Edge Lengths (I1MT-R-l∞)

We consider the model underl∞ norm as follows:I1MT-R-l∞. When l_e<0 for each e∈E and the criterion function C(a):RE→R is a function such that C(a)=||ca||∞, where c is the cost vector, ce>0 is the cost of decreasing le by one unit for each e∈E, and ∥u∥∞=maxe∈E|ue| stands for l∞ norm of vector u, we call (4) Problem I1MT-R-l∞, which is the inverse 1-median problem on trees with variable real edge lengths under l∞ norm.Also from a similar discussion in Section3.2.1, Problem I1MT-R-l∞can be formally described as follows:
(19)minmaxe∈ESce(le-xe)s.t.∑e∈P(v)Bexe≤0,∀v∈VS∖{v0},l_e≤xe≤le,∀e∈ES.
Let te′=Be(xe-l_e), te=Be(le-l_e), he=ce/Be, Ly(P(v))=∑e∈P(v)ye, and U(v)=-∑e∈P(v)Bel_e for each e∈ES and v∈VS∖{v0}. First, we suppose that he=1 for each e∈ES. Equation (19) can be formulated as the following program:
(20)minmaxe∈ES(te-te′)s.t.Lt′(P(v))≤U(v),∀v∈VS∖{v0},0≤te′≤te,∀e∈ES.In [20], the authors presented a strongly polynomial time algorithm to solve this type of problem, which runs in O(|V|3) time. Because the network concerned here is tree network, we now give a simplified procedure to solve (20) which runs in O(|V|2) time.On treeTS, if max{Lt(P(v))-U(v)∣v∈VS∖{v0}}≤0, we need do nothing. Hence, we only consider the case that max{Lt(P(v))-U(v)∣v∈VS∖{v0}}>0. Clearly, the optimal solution t* satisfies max{Lt*(P(v))-U(v)∣v∈VS∖{v0}}=0. Denote θ*=∥t-t*∥∞, then for any edge e∈ES, we have te*=max{te-θ*,0}.As the procedure in [20], first we sort the edges by their lengths in an increasing order. Beginning with the shortest edge, say e′, set te′=te-te′ for each e∈ES, and check if max{Lt′(P(v))-U(v)∣v∈VS∖{v0}}<0. If yes, we know that the lengths are overreduced and θ*<te′. If max{Lt′(P(v))-U(v)∣v∈VS∖{v0}}=0, t*=t′ is the optimal solution. If max{Lt′(P(v))-U(v)∣v∈VS∖{v0}}>0, then  θ*>te′, and in this case we contract the edges e with te′=0 into vertices and repeat the process on the resulted network with respect to t′. Since at least one vertex disappears in each contraction, the procedure has at most |V| iterations. For the time complexity, to find the shortest edge e′ can be completed in O(|E|) time, and in each iteration, the time for checking if max{Lt′(P(v))-U(v)∣v∈VS∖{v0}}<0 is O(|V|). Hence, the complexity of this procedure is O(|V|2). In the following, we assume that θ*<te′, which means that the preliminary procedure is finished while the optimality has not been reached.Because the path between any two vertices on tree network is unique, letQ denotes the set of vertices which does not satisfy the upper bound demand. Let |P| be the number of edges of path P. Let
(21)θ=max{Lt(P(v))-U(v)|P(v)|∣v∈Q},
then θ*=θ is the optimal reduction.Remark 7.
Note that whenhe≠1 for each e∈ES, (20) can be formulated as the following program:
(22)minmaxe∈EShe(te-te′)s.t.Lt′(P(v))≤U(v),∀v∈VS∖{v0},0≤te′≤te,∀e∈ES.In this case, we denoteθ*=∥h(t-t*)∥∞; then for any edge e∈ES, we have te*=max{te-θ*/he,0}. We sort the edges by tehe(e∈ES) in an increasing order to conduct the preliminary procedure to ensure that θ*<te′he′, where e′ is the edge satisfying te′he′=min{tehe∣e∈ES}. Let
(23)θ=max{Lt(P(v))-U(v)∑e∈P(v)1/he∣v∈Q},
then θ*=θ is the optimal reduction. Similar discussions show that the above procedure correctly solves program (22), and its computational complexity is O(|V|2).From the above analysis, we have the following theorem.Theorem 8.
Problem I1MT-R-l∞ can be solved in O(|V|2) time.


## 3.2.1. The Model Underl1 Norm with Variable Real Edge Lengths (I1MT-R-l1)

In this section, we consider the following inverse 1-median problem on trees with variable real edge lengths underl1 norm when edge length increase is forbidden.I1MT-R-l1. When l_e<0 for each e∈E and the criterion function C(a):RE→R is a function such that C(a)=ca, where c is the cost vector and ce>0 is the cost of decreasing le by one unit for each e∈E, we call (4) Problem I1MT-R-l1, which is the inverse 1-median problem on trees with variable real edge lengths under l1 norm.Problem I1MT-R-l1can be formally described as follows:
(13)min∑e∈Ece(le-xe)s.t.∑e∈P(v0,v¯)Bexe≤0,∀v¯∈V∖{v0},l_e≤xe≤le,e∈E.For a pathP(v0,vr)=v0,e1,v1,e2,v2,…,vr-1,er,vr, suppose that Bei-1>0 and Bei≤0, where 2≤i≤r. Denote the optimal solution of Problem I1MT-R-l1 by lopt. We have the following.Theorem 4.
l
e
j
o
p
t
=
l
e
j for j=i,i+1,…,r.Proof.
By (9), clearly Bej>0 for j=1,2,…,i-1 and Bei≤0 for j=i,i+1,…,r. Suppose to the contrary that there exists an edge ek∈P(vi-1,vr) such that  l_ek≤lekopt<lek. Similar to the proof of Case 2 in Theorem 3, we define a new feasible solution l′′ such that lek′′=lek and lej′′=lejopt when j≠k. Then we have ∑e∈P(v0,v)Bele′′≤∑e∈P(v0,v)Beleopt≤0 for each vertex v∈V. But ce(le-le′′)<ce(le-leopt), and therefore c(l-l′′)<c(l-lopt), a contradiction to the fact that lopt is the optimal solution of Problem I1MT-R-l1. This completes the proof.From Theorem4, we only need to determine the optimal adjusted edge lengths leopt with Be>0. We construct the subtree TS=(VS,ES) of T with ES={e∣Be>0,e∈E}, TS=T[ES], and VS=V(TS). Clearly, v0∈VS. Regard TS as a directed tree with the orientation from the root v0 to all leaves (e.g., by conducting the breadth-first method). For each v∈VS, let P(v) denote the path from v0 to v on the tree TS. We can simplify (13) as
(14)min∑e∈ESce(le-xe)s.t.∑e∈P(v)Bexe≤0,∀v∈VS∖{v0},l_e≤xe≤le,∀e∈ES.In [16, 17], the authors considered the shortest path improvement problem, which is how to shorten the lengths of edges with as less cost as possible such that the distances between specified sources and terminals are reduced to the required bounds. It is not difficult to see that (14) is in fact a shortest path improvement problem for tree networks with single source v0 and the required bound 0 under l1 norm. Let θe=Be(le-xe)≥0, be=Be(le-l_e)>0, and pe=ce/Be>0 for each e∈ES. Let rv=∑e∈P(v)Bele>0 for each v∈VS. Equation (14) can be formulated as the following linear program:
(15)min∑e∈ESpeθes.t.∑e∈P(v)θe≥rv,∀v∈VS∖{v0},0≤θe≤be,∀e∈ES.
Equation (15) is a combinatorial linear program and can be solved by a strongly polynomial time algorithm [18]. Moreover, (15) can be solved much faster [16, 17]. In [16], the authors presented a steepest descent-type combinatorial algorithm to solve this problem, which runs in O(|V|2) time. In [17], the authors formulated the dual problem of (15) as a minimum cost flow problem on a two-terminal serial-parallel graph and then gave an algorithm to obtain the primal optimal solution of (15), with the whole procedure running in O(|V|log|V|) time.From the above analysis, we have the following theorem.Theorem 5.
Problem I1MT-R-L1 can be solved in O(|V|log|V|) time.


## 3.2.2. The Model under Hamming Distance with Variable Real Edge Lengths (I1MT-R-H)

Now we consider the model under Hamming distance. The definition of Hamming distance will be given in this section.I1MT-R-H. When l_e<0 for each e∈E and ce>0 is the cost of decreasing le for each e∈E, we call the following program (16) Problem I1MT-R-H, which is the inverse 1-median problem on trees with variable real edge lengths under Hamming distance:
(16)min∑e∈EceH(xe,le)s.t.∑e∈P(v0,v¯)Bexe≤0,∀v¯∈V∖{v0},l_e≤xe≤le,e∈E,where the Hamming distance H(xe,le) is defined as
(17)H(xe,le)={0,xe=le,1,xe≠le.From a similar discussion in the former Section3.2.1, Problem I1MT-R-H can be formulated as follows:
(18)min∑e∈ESceH(xe,le)s.t.∑e∈P(v)Bexe≤0,∀v∈VS∖{v0},l_e≤xe≤le,∀e∈ES.
Equation (18) is a shortest path improvement problem for tree networks with single source v0 and the required bound 0 under Hamming distance [19]. In [19], the authors proved that even if the network is a chain network, the problem is still NP-hard. So, we have the following.Theorem 6.
Problem I1MT-R-H is NP-hard.


## 3.2.3. The Model underl∞ Norm with Variable Real Edge Lengths (I1MT-R-l∞)

We consider the model underl∞ norm as follows:I1MT-R-l∞. When l_e<0 for each e∈E and the criterion function C(a):RE→R is a function such that C(a)=||ca||∞, where c is the cost vector, ce>0 is the cost of decreasing le by one unit for each e∈E, and ∥u∥∞=maxe∈E|ue| stands for l∞ norm of vector u, we call (4) Problem I1MT-R-l∞, which is the inverse 1-median problem on trees with variable real edge lengths under l∞ norm.Also from a similar discussion in Section3.2.1, Problem I1MT-R-l∞can be formally described as follows:
(19)minmaxe∈ESce(le-xe)s.t.∑e∈P(v)Bexe≤0,∀v∈VS∖{v0},l_e≤xe≤le,∀e∈ES.
Let te′=Be(xe-l_e), te=Be(le-l_e), he=ce/Be, Ly(P(v))=∑e∈P(v)ye, and U(v)=-∑e∈P(v)Bel_e for each e∈ES and v∈VS∖{v0}. First, we suppose that he=1 for each e∈ES. Equation (19) can be formulated as the following program:
(20)minmaxe∈ES(te-te′)s.t.Lt′(P(v))≤U(v),∀v∈VS∖{v0},0≤te′≤te,∀e∈ES.In [20], the authors presented a strongly polynomial time algorithm to solve this type of problem, which runs in O(|V|3) time. Because the network concerned here is tree network, we now give a simplified procedure to solve (20) which runs in O(|V|2) time.On treeTS, if max{Lt(P(v))-U(v)∣v∈VS∖{v0}}≤0, we need do nothing. Hence, we only consider the case that max{Lt(P(v))-U(v)∣v∈VS∖{v0}}>0. Clearly, the optimal solution t* satisfies max{Lt*(P(v))-U(v)∣v∈VS∖{v0}}=0. Denote θ*=∥t-t*∥∞, then for any edge e∈ES, we have te*=max{te-θ*,0}.As the procedure in [20], first we sort the edges by their lengths in an increasing order. Beginning with the shortest edge, say e′, set te′=te-te′ for each e∈ES, and check if max{Lt′(P(v))-U(v)∣v∈VS∖{v0}}<0. If yes, we know that the lengths are overreduced and θ*<te′. If max{Lt′(P(v))-U(v)∣v∈VS∖{v0}}=0, t*=t′ is the optimal solution. If max{Lt′(P(v))-U(v)∣v∈VS∖{v0}}>0, then  θ*>te′, and in this case we contract the edges e with te′=0 into vertices and repeat the process on the resulted network with respect to t′. Since at least one vertex disappears in each contraction, the procedure has at most |V| iterations. For the time complexity, to find the shortest edge e′ can be completed in O(|E|) time, and in each iteration, the time for checking if max{Lt′(P(v))-U(v)∣v∈VS∖{v0}}<0 is O(|V|). Hence, the complexity of this procedure is O(|V|2). In the following, we assume that θ*<te′, which means that the preliminary procedure is finished while the optimality has not been reached.Because the path between any two vertices on tree network is unique, letQ denotes the set of vertices which does not satisfy the upper bound demand. Let |P| be the number of edges of path P. Let
(21)θ=max{Lt(P(v))-U(v)|P(v)|∣v∈Q},
then θ*=θ is the optimal reduction.Remark 7.
Note that whenhe≠1 for each e∈ES, (20) can be formulated as the following program:
(22)minmaxe∈EShe(te-te′)s.t.Lt′(P(v))≤U(v),∀v∈VS∖{v0},0≤te′≤te,∀e∈ES.In this case, we denoteθ*=∥h(t-t*)∥∞; then for any edge e∈ES, we have te*=max{te-θ*/he,0}. We sort the edges by tehe(e∈ES) in an increasing order to conduct the preliminary procedure to ensure that θ*<te′he′, where e′ is the edge satisfying te′he′=min{tehe∣e∈ES}. Let
(23)θ=max{Lt(P(v))-U(v)∑e∈P(v)1/he∣v∈Q},
then θ*=θ is the optimal reduction. Similar discussions show that the above procedure correctly solves program (22), and its computational complexity is O(|V|2).From the above analysis, we have the following theorem.Theorem 8.
Problem I1MT-R-l∞ can be solved in O(|V|2) time.


## 4. Conclusion

In this paper, we discussed the inverse 1-median problem with variable edge lengths on tree networks. We showed that this problem is solvable in linear time with variable nonnegative edge lengths under all kinds of norms. For the case when negative edge lengths are allowable, by formulating this problem to some known combinatorial optimization problems, we showed that this problem is NP-hard under Hamming distance and we proposed strongly polynomial time algorithms underl1 and l∞ norms, respectively.As a future research topic, it will be meaningful to consider the problem on other networks such as the interval graph, the cactus graph, and the block graph, especially under the Hamming distance. We know that Algorithm2 can solve Problem I1MT-N under all kinds of norms. But when negative edge lengths are allowable, we only dealt with the problems under the constraint that the edge length increase is forbidden. So we can further study the complexity of the problems such that the edge lengths can either be reduced or increased. In addition, for the inverse p-median problems for p≥2, designing the optimal or approximation algorithms and analysing their computational complexities are also promising.



---

*Source: 313868-2013-04-16.xml*