The Uniform Cost Reverse 1-Centdian Location Problem on Tree Networks with Edge Length Reduction

Abstract

In location theory, the 1-centdian function is a convex combination of the 1-median and the 1-center functions. We consider the uniform cost reverse 1-centdian problem on networks, where edge lengths are reduced within a given budget such that the 1-centdian function at a prespecified point on the network is minimized. We first prove that the problem on general networks is NP-hard by reducing the set cover problem to it. Then, we focus on the special case of the problem on tree networks. Based on the strategy that we reduce either one edge or several edges simultaneously in each step to obtain an optimal solution, we develop a combinatorial algorithm that solves the corresponding problem on trees in quadratic time.

1 Introduction

Classical location theory aims to find the optimal location of one or several new facilities. For the location problem concerning public services such as warehouses, supermarkets, etc., we use the median function. On the other hand, the center function is applied to model the location problem regarding emergency services such as hospitals and fire stations. Location problems on the plane and on networks have been intensively studied, for example, by Das et al. [9], Drezner and Hamacher [10], Eiselt and Marianov [11], and Kariv and Hakimi [19, 20]. Halpern [16, 17] further considered a convex combination of the median and the center objective functions in his proposed locational model for the case where both public services and emergency services are taken into account, for instance, the location of a school. He also proposed a linear time algorithm for the problem on trees and a polynomial time algorithm for the problem on general networks. Since then, the centdian location problem has become an interesting topic in the field of locational analysis with numerous publications. A few of them are Brito et al. [26] on the 2-facility centdian problem, Tamir et al. [29] on the p-centdian problem on trees, Kang et al. [18] on the connected p-centdian problem on blockgraphs, and many references therein.

As a counterpart to the classical location problem, the previous researchers proposed two types of modern problems concerning adjusting the input data in order to change the structure of the original problem with respect to a task (given by a decision maker). One of them is the inverse location problem, which seeks to change the parameters at a minimum total cost so as to make prespecified facilities optimal in the modified network. The inverse location problem has been investigated due to their potential in real life applications and in theory (see [2, 3, 23, 25, 27]). On the other hand, the reverse location problem aims to modify parameters of a network subject to a given budget constraint such that the network is improved (decided by a decision maker) as much as possible. In the scope of this paper, we focus on the reverse location problem. Hence, we review the existing literature concerning the reverse location problem to ease the readers in the following discussion.

The reverse location problem first appeared in the seminal works of Berman et al. [5, 6] in terms of improving the minisum and minimax functions on a network by reducing the edge lengths. The authors considered the reverse 1-median problem on trees with a linear time algorithm and proved that the corresponding problem on networks is NP-hard. They also proposed a heuristic approach for the problem on general networks. Additionally, the authors proposed an iterative approach to the reverse 1-center problem on trees without detailed analysis on the complexity and the correctness of the algorithm. They also proved NP-hardness of the problem on general networks and proposed a heuristic approach as well. Since then, the reverse location problem has garnered interest among researchers in the location problem community. Reverse 1-center location problem on unweighted trees was investigated by Zhang et al. [30, 31]. They proposed minimum cut approaches for tackling the problem in $O(n^{2} \log n)$ time, where n is the number of vertices in the underlying tree. Later, Nguyen [24] considered the uniform-cost reverse 1-center problem on weighted trees and developed a quadratic algorithm for the problem. Meanwhile, concerning the reverse 1-median problem, Burkard et al. [7] proved further that the problem on networks is NP-hard and the optimal solution cannot be approximated by a constant number. They also devised a linear time algorithm to solve the corresponding problem on cycles. Also, Burkard et al. [8] showed that both the reverse 2-median problem on trees and the reverse 1-median problem on uni-cyclic graphs can each be reduced to an equivalent 2-median problem on paths. This result helped to solve the two mentioned problems in $O(n\log n)$ time. For the reverse version of the obnoxious location problem, that is, one or several servers are not desirable in the network system, Alizadeh and Etemad [4] developed a linear time algorithm to solve the problem under the rectilinear norm or the Hamming distance. Furthermore, the reverse selective obnoxious center location problem on trees can be solved in quadratic time generally and in linear time for the uniform cost situation (see Etemad and Alizadeh [12]). Another type of network improving problem is the upgrading or downgrading problem. In this case, there is no prespecified facility and one or several facilities are optimally located after modifying the network. Interested reader can refer to Afrashteh et al. [1], Gassner [13, 14], and Sepasian [28] for algorithmic approaches related to the upgrading and downgrading problems.

From previous literature, we observe that the reverse 1-median and the reverse 1-center problems have already been investigated with some efficient solution algorithms found. However, the reverse 1-centdian problem has not been studied so far although the classical 1-centdian problem has been extensively studied. Due to the importance of the 1-centdian function in modeling real life problems, the corresponding reverse 1-centdian problem is promising in theory and in application as well. For example, let a network and a predetermined vertex, designating the location of a supplier, be given. In the network, each vertex plays the role of a demander and each edge represents the connection between two demanders. The size of the population of a demander is the associated vertex weight and the travel time between two demanders of the network is represented by the edge length. The efficiency of the given supplier is measured by the 1-centdian function according to its special purpose, serving as a public or emergency service like a school or a hospital. In order to improve the efficiency of the supplier, a budget is provided. However, the supplier cannot be moved to other locations due to security and cost reasons. Instead, we can shorten the travel time between adjacent vertices of the network by improving the edge capacities or modernizing the related technologies and this incurs relevant cost. Hence, the question is how to use the budget to improve the efficiency of the supplier in an optimal way. This real-life situation is indeed modeled as a reverse 1-centdian problem on networks.

We focus in this paper the algorithmic approach to the reverse 1-centdian problem on networks and organize the paper as follows. Section 2 introduces fundamental concepts of the reverse 1-centdian problem on networks. We also derive NP-hardness result for the problem in this section. In Section 3, we study the problem on tree networks and developed a novel O(n²) algorithm for the problem on a tree with n vertices.

2 Problem Definition and Complexity

We first introduce some basic concepts concerning the 1-centdian location problem on a network (or graph). Let an undirected connected graph G = (V,E,w,ℓ) be given with V (|V | = n) and E being respectively the vertex set and the edge set. Furthermore, the function $w: V \to \mathbb R_{+}$ maps each vertex v to a positive vertex weight, say w(v). Also, the function $\ell : E \to \mathbb R_{+}$ maps each edge e to a positive edge length, say ℓ(e). Each edge of the graph can be considered as a continuous interval containing points of the graph. The distance d_ℓ(a,b) between two points a and b is the length of the shortest path P(a,b) connecting them with respect to ℓ. The 1-centdian function at a point ρ, according to Halpern [16, 17], can be presented as a convex combination of the 1-median and the 1-center function at the same point, that is,

$$ \lambda\sum\limits_{v\in V}w(v)d_{\ell}(v,\rho)+(1-\lambda)\max\limits_{v\in V}\{w(v)d_{\ell}(v,\rho)\}, $$

where λ ∈ (0,1). In this work, readers are assumed to be familiar with the 1-median function ${\sum }_{v\in V}w(v)d_{\ell }(v,\rho )$ and the 1-center function $\max \limits _{v\in V}w(v)d_{\ell }(v,\rho )$ on a network G. Equivalently, the 1-centdian problem is to find a point ρ that minimizes

$$ F(\rho) := \sum\limits_{v\in V}w(v)d_{\ell}(v,\rho)+\alpha\max_{v\in V}w(v)d_{\ell}(v,\rho) $$

for α := (1 − λ)/λ. Hence, from here onwards, we regard the function F(ρ) as the 1-centdian function.

Assuming that we have found a desired position on a network G to locate a facility and it can not be relocated due to security or logistics reasons. Then, the decision maker would like to improve the efficiency of the network by reducing the objective function, say the 1-centdian function, at the prespecified facility location as much as possible by reducing the distances between servers and customers within a given budget. The corresponding model is the so-called reverse 1-centdian problem on networks.

In order to formulate the model, let a prespecified point on G, where the server is located, be given. One always assumes that the point, denoted by v^∗, is a vertex as otherwise, we split the edge that contains v^∗ into two edges to induce a new graph. We can reduce the distances from customers to v^∗ by reducing the length of each edge e by x(e). The modified length of e is written as $\widetilde {\ell }(e) := \ell (e) - x(e)$. Additionally, for each e ∈ E, the modified length $\widetilde {\ell }(e)$ is restricted to a given bound, say $\widetilde {\ell }(e) \in [\underline {\ell }(e), \ell (e)]$. We set $\bar {x}(e) := \ell (e) - \underline {\ell }(e)$ to be the largest possible modification of e in E. In real life situation, the distance between vertices are always positive, this implies that the length of each edge is also positive, that is, $\underline {\ell }(e) > 0$ or $\bar {x}(e) < \ell (e)$ for all e ∈ E. We denote by c(e) the (positive) cost to modify an edge e and it is proportional to the magnitude of modification. The total cost of modifying the edge lengths is limited within a given budget B. Let $d_{\widetilde {\ell }}$ be the distance function with respect to the new edge lengths $\widetilde {\ell }$. Then, the reverse 1-centdian problem on G can be formulated as follows.

$$ \begin{array}{@{}rcl@{}} &&\min\widetilde{F}(v^{\ast}):=\sum\limits_{v\in V}w(v)d_{\widetilde{\ell}}(v,v^{\ast})+\alpha\max_{v\in V}w(v)d_{\widetilde{\ell}}(v,v^{\ast}),\\ &&\text{s.t. }~~\widetilde{\ell}(e)=\ell(e)-x(e),~\forall e\in E,\\ &&\qquad\sum\limits_{e\in E}c(e)x(e)\le B,\\ &&\qquad 0\le x(e)\le \bar{x}(e),~\forall e\in E. \end{array} $$

In this paper, we consider the uniform cost situation, that is, c(e) := C for all e ∈ E. Moreover, one can always assume that c(e) := 1 for all e ∈ E as otherwise, we can reduce to this case with the new budget $B^{\prime } := B/C$. With our assumption, the budget constraint is translated into ${\sum }_{e\in E}x(e) \le B$. Let us further make an assumption that ${\sum }_{e\in E}\bar {x}(e) > B$ since otherwise we can get a trivial optimal solution $x(e) := \bar {x}(e)$ for all e ∈ E.

We first consider the complexity of the problem on general networks.

Theorem 1

The reverse 1-centdian problem is NP-hard even on unweighted networks.

Proof

We start with an instance of the Set Cover Problem (SC) given below:

Given::

A finite set E = {1,2,…,n}, a collection E₁,…,E_m of subsets of E whose union is E, and a number k ≤ m.

Question::

Does there exist k subsets in {E₁,…,E_m} such that their union is exactly the ground set E?

The (SC) problem is NP-complete (see Garey and Johnson [15]).

The decision version of the reverse 1-centdian problem on networks (RCPN) is stated as follows:

Given::

An instance of the unweighted network G = (V,E,w,ℓ), that is, w(v) = 1 for all v ∈ V, with a prespecified vertex v^∗, modification bounds $\bar {x}(e)$ for all e in E, a budget B, and a value M.

Question::

Does there exist an edge length modification such that the total cost is limited within B and the 1-centdian function at v^∗ that is at most M?

We prove that (RCPN) is NP-hard by reducing an instance of (SC) to someone in polynomial time and prove that the answer to (SC) is ‘yes’ if and only if the answer to (RCPN) is ‘yes’. Given an instance of (SC), we construct an instance of (RCPN) as follows.

• The vertex set is V := {v^∗}∪{u_i : i = 1,…,m}∪{v_j : j = 1,…,n} and the edge set is E := E₁ ∪ E₂, where E₁ := {(v^∗,u_i) : i = 1,…,m} and E₂ := {(u_i,v_j) : i = 1,…,m,j = 1,…,n and j ∈ E_i}.

• The weight of each vertex is V is 1. The lenghs are defined as ℓ(e) := 2 if e ∈ E₁ and ℓ(e) := 1 if e ∈ E₂. Modification bounds are $\bar {x}(e) = 1$ if e ∈ E₁ and $\bar {x}(e) = 0$ if e ∈ E₂.

• We set B := k and M := 2m + 2n − k + 2.

• Furthermore, we choose α = 1, that is, the objective function can be written as

  $$ F(v^{\ast}) = \sum\limits_{v\in V}d_{\ell}(v,v^{\ast}) + \max_{v\in V}d_{\ell}(v,v^{\ast}). $$

If the answer to (SC) is ‘yes’, we obtain a collection of subsets $E_{i_{1}},E_{i_{2}},\ldots ,E_{i_{k}}$ such that $\bigcup _{j=1}^{k} E_{i_{j}} = E$. We set $x(v^{\ast },u_{i_{j}}) := \bar {x}(v^{\ast },u_{i_{j}}) = 1$ for j = 1,…,k and other edge lengths are not modified. By elementary computations, the total cost is k and the 1-centdian function at v^∗ with respect to the modified graph is 2m + 2n − k + 2. Hence, the answer to (RCPN) is ‘yes’.

Conversely, we assume that there exists a modification of the edge lengths within a budget k such that the objective function at v^∗ is at most 2m + 2n − k + 2. As ${\sum }_{e \in E_{1}}\bar {x}(e) = m > k$, we can also assume that the modification cost is exactly k, that is, ${\sum }_{e\in E_{1}}x(e) = k$, because otherwise, we can reduce the edge lengths further without increasing the objective function at v^∗. Based on the structure of the graph G, we obtain that

$$ \sum\limits_{v \in V_{1}}d_{\widetilde{\ell}}(v,v^{\ast}) = \sum\limits_{v \in V_{1}}d_{\ell}(v,v^{\ast}) - \sum\limits_{e\in E_{1}}x(e) = 2m-k $$

and $d_{\widetilde {\ell }}(v,v^{\ast }) \geq 2$ for all v ∈ V₂. Therefore, we obtain

$$ \sum\limits_{v\in V}d_{\widetilde{\ell}}(v,v^{\ast}) = \sum\limits_{v \in V_{1}}d_{\widetilde{\ell}}(v,v^{\ast}) + \sum\limits_{v \in V_{2}}d_{\widetilde{\ell}}(v,v^{\ast}) \geq 2m -k + 2n $$

and

$$ \max\limits_{v\in V}d_{\widetilde{\ell}}(v,v^{\ast}) \geq 2. $$

This implies that the 1-centdian objective value is always at least 2m + 2n − k + 2. By the hypothesis, the objective function is exactly 2m + 2n − k + 2 and thus $d_{\widetilde {\ell }}(v,v^{\ast }) = 2$ for all v ∈ V₂. Let us denote by $\mathcal I:= \{i\in \{1,\ldots ,m\}:x(v^{\ast },u_{i}) = 1\}$. Then, we get $|\mathcal {I}| \leq k$, $d_{\widetilde {\ell }}(u_{j},v^{\ast }) = 1$ if $j \in \mathcal I$, and $d_{\widetilde {\ell }}(u_{j},v^{\ast }) > 1$ otherwise. As $d_{\widetilde {\ell }}(v,v^{\ast }) = 2$ for all v ∈ V₂, the shortest path from a vertex v ∈ V₂ to v^∗ must contain a vertex u_i for some $i \in \mathcal I$. Hence, it implies that $\cup _{i\in \mathcal I}E_{i} = E$. In other words, the answer to (SC) is ‘yes’. □

By Theorem 1, we can hardly find an algorithm that solves the (RCPN) problem in polynomial time unless P = NP. It is interesting to further consider special cases of the problem with polynomial time solution algorithms. In the next section, we study the reverse 1-centdian location problem on tree networks.

3 Reverse 1-Centdian Problem on Trees

In this section, we focus on the reverse 1-centdian problem on a tree (RCPT), say T = (V,E,w,ℓ). In the given tree, the path P(v,v^∗) connecting a vertex v and the prespecified vertex v^∗ is unique for each v in V. We can write $d_{\widetilde {\ell }}(v,v^{\ast }) := d_{\ell }(v,v^{\ast }) - {\sum }_{e\in P(v,v^{\ast })}x(e)$ and hence the 1-centdian function is a decreasing function on the modification of edge lengths. Based on this fact, we deliver a trivial but useful result that helps to understand the structure of an optimal solution of the (RCPT) problem.

Proposition 1

The budget constraint holds with equality for every optimal solution of the (RCPT) problem.

By Proposition 1, we can restate the budget constraint as ${\sum }_{e\in E}x(e) = B$ and denote by

$$ \mathcal F:= \left\{(x(e))_{e\in E}: \sum\limits_{e\in E}x(e) = B \text{ and } 0\le x(e)\le \bar{x}(e) \text{ for all } e\in E\right\}, $$

the set of feasible solutions to the (RCPT) problem. The 1-centdian objective function is said to be improved by $\mathcal R$ for $(x(e))_{e\in E} \in \mathcal F$ if $\mathcal R:=F(v^{\ast }) - \widetilde {F}(v^{\ast })$, where $\widetilde {F}(v^{\ast })$ is the 1-centdian function at v^∗ with respect to the modification (x(e))_e∈E. As the aim of (RCPT) is to minimize the 1-centdian function $\widetilde {F}(v^{\ast })$, it is equivalent to finding a feasible solution $(x(e))_{e \in E}\in \mathcal F$ which maximizes the improvement of the objective function.

3.1 Problem with a Sufficiently Small Budget B := ε

From here onwards, we root the tree T at the prespecified vertex v^∗. An edge e := (u,v), written in this ordering, means that u is a parent of v or v is a child of u. Observe that the (length) reduction of an edge e = (u,v) can be shifted to an edge along the path P(u,v^∗) if there exists an edge e^′∈ P(u,v^∗) with $\bar {x}(e^{\prime }) > 0$. This shift helps to reduce the 1-centdian value at v^∗ even further without increasing the cost. An edge e = (u,v) with $\bar {x}(e) > 0$ is, by definition, a candidate edge if no edge $e^{\prime }\in P(u, v^{\ast })$ exists such that $\bar {x}(e^{\prime })>0$. In particular, if e = (v^∗,v) and $\bar {x}(e)>0$, then e is a candidate edge. Also, we denote by $\mathcal C$ the set of candidate edges and focus on the edges in $\mathcal C$ when considering edges to be reduced.

Let us denote by $\mathcal T$ the maximal subtree of T with v^∗ in $\mathcal T$ and without any candidate edge. Let $\mu _{1} := \max \limits _{v \in V(\mathcal T )}w(v)d_{\ell }(v,v^{\ast })$ be the maximum weighted distance from vertices in $\mathcal T$ to the vertex v^∗. If $\mu _{1} = \max \limits _{v \in V}w(v)d_{\ell }(v,v^{\ast })$, the 1-center part $\max \limits _{v \in V}w(v)d_{\widetilde {\ell }}(v,v^{\ast })$ cannot be reduced any further. Then, the (RCPT) problem reduces to an equivalent reverse 1-median problem on the same tree and can be solved in linear time by Berman et al. [5]. Therefore, we can assume that $\mu _{1} < \max \limits _{v \in V}w(v)d_{\ell }(v,v^{\ast })$ with respect to the current subtree $\mathcal T$ and the tree T. This condition can be checked efficiently as finding μ₁ and $\max \limits _{v \in V}w(v)d_{\ell }(v,v^{\ast })$ can be done in linear time by a breadth first search (BFS) approach.

Now we aim to find which edges in $\mathcal C$ should be reduced to attain the maximum improvement for a sufficiently small fixed cost ε. For each candidate edge $e := (u,v) \in \mathcal C$, we denote by T_e the subtree rooted at v and W(T_e) the total weight of vertices in T_e. As the 1-centdian value is dependent on both the 1-median function ${\sum }_{u\in V}w(u)d_{\widetilde {\ell }}(u,v^{\ast })$ and the 1-center function $\max \limits _{u\in V}w(u)d_{\widetilde {\ell }}(u,v^{\ast })$, we now analyze the reduction of these functions with respect to edge length modification.

If we reduce a single edge e in $\mathcal C$ by ε, it is easy to verify that the 1-median function is reduced by W(T_e)ε. We set $e_{\max \limits }:=\arg \max \limits _{e := (u,v)\in \mathcal C}W(T_{e})$, that is, a specific candidate edge for which the corresponding tree has the largest total vertex weights. Then, reducing $e_{\max \limits }$ by ε yields the maximum reduction of the 1-median function, that is, by $W(T_{e_{\max \limits }})\varepsilon$.

For the 1-center function, we set

$$ v_{e} := \arg \min\left\{w(v): v\in T_{e} \text{ and } w(v)d_{\ell}(v^{\ast},v) = \max_{u\in V(T_{e})}w(u)d_{\ell}(v^{\ast},u)\right\}, $$

and call it an associated vertex in T_e. Note that, for a sufficiently small reduction of e, an associated vertex v_e satisfies $w(v_{e})d_{\widetilde {\ell }}(v_{e},v^{\ast }) = \max \limits _{u\in V(T_{e})}w(u)d_{\widetilde {\ell }}(u,v^{\ast })$.

In Fig. 1, for a candidate edge e = (v^∗,v₁), both v₃ and v₄ have maximum weighted distance to v^∗, namely 24. As w(v₃) < w(v₄), we set v_e := v₃.

Fig. 1

The associated vertex in $T_{(v^{\ast },v_{1})}$ (in red)

Let us abbreviate

$$ \mathcal{M} := \bigcup\limits_{e\in \mathcal C} \left\{v_{e}: w(v_{e})d_{\ell}(v^{\ast},v_{e}) = \max_{u\in V}w(u)d_{\ell}(v^{\ast},u)\right\} $$

the set of all associated vertices v_e such that the 1-center value of T is attained at these vertices. Furthermore, let $\mathcal C(\mathcal M) := \{e\in \mathcal C: v_{e}\in \mathcal M\}$ be the set of candidate edges with corresponding vertices in $\mathcal M$. In order to reduce the 1-center function, it is required to simultaneously reduce all the edges in $\mathcal C(\mathcal M)$. Therefore, we now analyze how much the 1-centdian function improves when all the edges in $\mathcal {C}({\mathscr{M}})$ (and no other edges) are reduced according to some modification satisfying a natural constraint. We will see that this analysis leads essentially to our main result.

Suppose e₁,e₂,…,e_k are all the edges in $\mathcal C({\mathscr{M}})$. By definition, $v_{e_{i}} = \arg \max \limits _{u \in V}w(u)$ d_ℓ(u,v^∗) for all i = 1,…,k. Suppose e_i is reduced by x(e_i) for each i = 1,…,k given a sufficiently small budget ε. To achieve maximum improvement, we may assume that ${\sum }_{j=1}^{k} x(e_{j})= \varepsilon$. More importantly, we suppose our edge length modification satisfies the following natural special condition:

$$ x(e_{1})w(v_{e_{1}})=x(e_{2})w(v_{e_{2}})=\cdots=x(e_{k})w(v_{e_{k}}). $$

(1)

We denote by $P := {\prod }_{j=1}^{k} w(v_{e_{j}})$, $w^{\prime }(v_{e_{i}}) :={\prod }_{j=1,j\ne i}^{k} w(v_{e_{j}})$, and $S :={\sum }_{i=1}^{k} w^{\prime }(v_{e_{i}})$. By elementary computation, for each i = 1,…,k, we get $x(e_{i}) =\frac {w^{\prime }(v_{e_{i}})}{S}\varepsilon$, or in other words

$$ x(e_{i}) = \frac{\varepsilon}{w(v_{e_{i}}) {\sum}_{j=1}^{k}\frac{1}{w(v_{e_{j}})}}. $$

(2)

Now, our constraint immediately implies that

$$ \max\limits_{u \in V}w(u)d_{\widetilde{\ell}}(u,v^{\ast}) = \max\limits_{u \in V}w(u)d_{\ell}(u,v^{\ast}) - x(e_{1})w(v_{e_{1}}). $$

Hence, the corresponding improvement of the 1-centdian function can be written as

$$ \begin{array}{@{}rcl@{}} \underbrace{\sum\limits_{i=1}^{k}x(e_{i})W(T_{e_{i}})}_{\text{1-median}} + \alpha \underbrace{x(e_{1})w(v_{e_{1}})}_{\text{1-center}} &=&\frac{1}{S}\left( \sum\limits_{i=1}^{k} w^{\prime}(v_{e_{i}})W(T_{e_{i}}) + \alpha P\right)\varepsilon\\ &=&\frac{P}{S}\sum\limits_{i=1}^{k}\left( \frac{W(T_{e_{i}})}{w(v_{e_{i}})} + \alpha\right)\varepsilon \\ &=& \frac{1}{{\sum}_{i=1}^{k}\frac{1}{w(v_{e_{i}})}}\left( \sum\limits_{i=1}^{k}\frac{W(T_{e_{i}})}{w(v_{e_{i}})} + \alpha\right)\varepsilon. \end{array} $$

Let

$$ {\varDelta}_{\mathcal M} := \left( \sum\limits_{e \in \mathcal C(\mathcal M)}\frac{W(T_{e})}{w(v_{e})} + \alpha\right)/\left( \sum\limits_{e \in \mathcal C(\mathcal M)}\frac{1}{w(v_{e})} \right) $$

(3)

and we can interpret ${\varDelta }_{\mathcal M}$ as the efficiency of reducing all edges in $\mathcal C(\mathcal M)$ according to (1). Moreover, we can trace back the reduction of the 1-centdian function based on the modifications of the edges in $\mathcal C(\mathcal M)$ and the efficiency ${\varDelta }_{\mathcal M}$. Indeed, by (2) we can write $\varepsilon := {\sum }_{e^{\prime } \in \mathcal C(\mathcal M)}\frac {1}{w(v_{e^{\prime }}))}w(v_{e})x(e)$ for any edge e in the set $\mathcal C(\mathcal M)$. The corresponding reduction of the 1-centdian function is thus presented by

$$ \sum\limits_{e^{\prime} \in \mathcal C(\mathcal M)}\frac{1}{w(v_{e^{\prime}})}{\varDelta}_{\mathcal M}w(v_{e})x(e) $$

(4)

for any edge $e \in \mathcal C(\mathcal M)$. Equations (3) and (4) can be calculated in $O(|\mathcal C(\mathcal M)|)$ time. As $|\mathcal C(\mathcal M)| \leq n$, the corresponding computation costs linear time in the worst case scenario.

We are now ready for our main result of this section.

Proposition 2

Let a sufficiently small budget ε be given. If ${\varDelta }_{\mathcal M} > W(T_{e_{\max \limits }})$, we reduce each edge in $\mathcal C(\mathcal M)$ according to (2) to obtain the maximum reduction of the 1-centdian function, namely ${\varDelta }_{{\mathscr{M}}}\varepsilon$. Otherwise, if ${\varDelta }_{\mathcal M} \leq W(T_{e_{\max \limits }})$, we reduce the edge $e_{\max \limits }$ to obtain the maximum reduction of the 1-centdian function, namely $W(T_{e_{\max \limits }})\varepsilon$.

Proof

Suppose that ${\varDelta }_{\mathcal M} > W(T_{e_{\max \limits }})$ and the edges e₁,e₂,…,e_k are reduced by x(e₁),x(e₂),…,x(e_k), where ${\sum }_{i=1}^{k} x(e_{i}) = \varepsilon$. First, we prove that to yield the maximum reduction of the 1-centdian function, all edges in $\mathcal C(\mathcal M)$ must be reduced or else it is better off just by reducing the single edge $e_{\max \limits }$. Indeed, assume not all edges in $\mathcal C({\mathscr{M}})$ are reduced. Then the 1-center part $\max \limits _{v\in V}w_{v}d_{\widetilde {\ell }}(v^{\ast },v)$ in the 1-centdian function is not reduced. Hence, the improvement is at most

$$ \sum\limits_{i=1}^{k} x(e_{i})W(T_{e_{i}}) \le W\left( T_{e_{\max}}\right) \sum\limits_{i=1}^{k} x(e_{i}) \le W\left( T_{e_{\max}}\right)\varepsilon. $$

Next, we prove that assuming we reduce exactly all edges in $\mathcal C(\mathcal M)$, then the modification satisfying condition (1) yields the maximum reduction to the 1-centdian function, namely ${\varDelta }_{\mathcal M}\varepsilon$ according to our analysis before. Suppose e₁,e₂,…,e_k are all the edges in $\mathcal C(\mathcal M)$ but condition (1) does not hold. Without loss of generality, $w(v_{e_{1}})x(e_{1}) \leq w(v_{e_{2}})x(e_{2}) \leq {\cdots } \leq w(v_{e_{k}})x(e_{k})$. Let i be the smallest index such that $w(v_{e_{i}})x(e_{i}) < w(v_{e_{i+1}})x(e_{i+1})$. Then, we consider $x^{\prime }(e_{i+1}), \ldots , x^{\prime }(e_{k})$ with $x^{\prime }(e_{s}) < x(e_{s})$ for all s = i + 1,…,k such that

$$ \begin{array}{@{}rcl@{}} w(v_{e_{1}})x(e_{1}) &=& w(v_{e_{2}})x(e_{2}) = {\cdots} =w(v_{e_{i}})x(e_{i}) = w(v_{e_{i+1}})x^{\prime}(e_{i+1})\\ & =& w(v_{e_{i+2}})x^{\prime}(e_{i+2}) = {\cdots} = w(v_{e_{k}})x^{\prime}(e_{k}). \end{array} $$

We set $\varepsilon _{1} := {\sum }_{r=1}^{i} x(e_{r}) + {\sum }_{s=i+1}^{k} x^{\prime }(e_{s})$ and $\varepsilon _{2} := {\sum }_{s=i+1}^{k}[x(e_{s}) - x^{\prime }(e_{s})]= \varepsilon - \varepsilon _{1}$. By the analysis before, the improvement of the 1-centdian function is

$$ \begin{array}{@{}rcl@{}} {\varDelta}_{\mathcal M}\varepsilon_{1} + \sum\limits_{s=i+1}^{k}W(T_{e_{s}})[x(e_{s}) - x^{\prime}(e_{s})] &\leq& {\varDelta}_{\mathcal M}\varepsilon_{1} + W(T_{e_{\max}}) \varepsilon_{2}\\ & < & {\varDelta}_{\mathcal M}(\varepsilon_{1} + \varepsilon_{2}) = {\varDelta}_{\mathcal M}\varepsilon. \end{array} $$

Finally, it remains to observe that if we reduce all edges in $\mathcal C(\mathcal M)$ according to condition (1) with budget ε₁ and also some other edges $e^{\prime }_{1},\ldots , e^{\prime }_{j}$ that are not in $\mathcal C(\mathcal M)$ with budget ε₂, then the improvement of the 1-centdian function is

$$ \begin{array}{@{}rcl@{}} {\varDelta}_{\mathcal M}\varepsilon_{1} + \sum\limits_{s=1}^{j}W(T_{e^{\prime}_{s}})x(e^{\prime}_{s}) &\leq& {\varDelta}_{\mathcal M}\varepsilon_{1} + W(T_{e_{\max}}){\sum}_{s=1}^{j} x(e^{\prime}_{s})\\ & <& {\varDelta}_{\mathcal M}(\varepsilon_{1} + \varepsilon_{2}) = {\varDelta}_{\mathcal M}\varepsilon. \end{array} $$

Therefore, our proof of the first part is complete.

Now, suppose ${\varDelta }_{\mathcal M} \leq W(T_{e_{\max \limits }})$. The preceding case analysis can be easily modified to show that the maximum reduction of the 1-centdian function is $W(T_{e_{\max \limits }})\varepsilon$. This can be achieved by reducing the edge $e_{\max \limits }$ by ε, noting that $\mathcal C(\mathcal M) \neq \{e_{\max \limits }\}$ (see the next remark). □

Remark 1

If $\mathcal C(\mathcal M) = \{e_{\max \limits }\}$, without relying on Proposition 2, it is obvious that reducing $e_{\max \limits }$ by ε leads to the maximum reduction of the 1-centdian function, namely, $(W(T_{e_{\max \limits }})+\alpha w(v_{e_{\max \limits }}))\varepsilon$. In this case, ${\varDelta }_{\mathcal M} = W(T_{e_{\max \limits }}) + \alpha w(v_{e_{\max \limits }}) > W(T_{e_{\max \limits }})$ and thus the choice of reduction is consistent with Proposition 2.

Remark 2

As the 1-center function is continuous on the edge lengths, we can choose ε to be sufficiently small such that $\mathcal C$, $\mathcal M$, and $\mathcal C(\mathcal M)$ do not change in the perturbed tree.

3.2 A Greedy Iterative Approach

We previously discussed which edges should be reduced for the maximum improvement of the 1-centdian function under a sufficiently small cost ε once $\mathcal C(\mathcal M)$ is known. Obviously, the set $\mathcal C(\mathcal M)$ depends directly on the sets $\mathcal C$ and $\mathcal M$. Throughout the reduction of edge lengths, the sets $\mathcal C$ and $\mathcal M$ may change. Hence, now we investigate the situations where one of the sets $\mathcal C$ and $\mathcal M$ changes.

Case 1. Where the set $\mathcal C$ of Candidate Edges Changes

Assuming that an edge e (which is either $e_{\max \limits }$ or is in $\mathcal C(\mathcal M)$) is reduced by $\bar {x}(e)$, its updated value of $\bar {x}(e)$ is 0 and thus e is not a candidate edge anymore. In this case, we apply a (BFS) approach to find a new candidate edge(s) within the subtree T_e to update $\mathcal C$ in O(|T_e|) time. Other related data must be updated accordingly as described below.

Part 1.

If ${\varDelta }_{\mathcal M} \leq W(T_{e_{\max \limits }})$, we reduce the edge $e := e_{\max \limits }$ and the 1-center function $\max \limits _{v\in V}w(v)d_{\widetilde {\ell }} (v,v^{\ast })$ is not reduced. If there is a vertex v in $T_{e_{\max \limits }}\cap \mathcal M$, we set $\mathcal M := \mathcal M \backslash \{v\}$ and $\mathcal C(\mathcal M) := \mathcal C(\mathcal M) \backslash \{e_{\max \limits }\}$. Otherwise, these sets $\mathcal M$ and $\mathcal C(\mathcal M)$ do not change. Moreover, we update $e_{\max \limits }$, the subtree $\mathcal T$, and the value μ₁ according to the new candidate set $\mathcal C$. To summarize, we have to update $\mathcal C$, $\mathcal M$, $\mathcal C(\mathcal M)$, $\mathcal T$, μ₁, $e_{\max \limits }$, and ${\varDelta }_{\mathcal M}$ accordingly. The complexity of this part is $O(|T_{e_{\max \limits }}|+|\mathcal C(\mathcal M)|)$ due to the (BFS) approach and the complexity of computing ${\varDelta }_{\mathcal M}$. As both $|T_{e_{\max \limits }}|$ and $|\mathcal C(\mathcal M)|$ are at most n, the complexity of this part is linear.

We study an instance in Fig. 2 with α = 1 and $\mathcal C =\{(v_{1},v_{2}),(v_{1},v_{4})\}$. Furthermore, $\mathcal T = \{v^{\ast },v_{1}\}$ with μ₁ = 2. We can compute $e_{\max \limits } = \{(v_{1},v_{4})\}$ with $W(T_{e_{\max \limits }}) = 13$. As $\mathcal M =\{v_{3},v_{5}\}$ and $\mathcal C(\mathcal M) = \mathcal C$, we obtain ${\varDelta }_{\mathcal M} = 23/3 < W(T_{e_{\max \limits }})$. Thus, we reduce $e_{\max \limits } = \{(v_{1},v_{4})\}$. Assuming that $\bar {x}(v_{1},v_{2}) = \bar {x}(v_{1},v_{4}) = \bar {x}(v_{4},v_{5}) = \bar {x}(v_{4},v_{6}) = 1$, after reducing (v₁,v₄) by 1, we update $\mathcal C = \{(v_{1},v_{2}),(v_{4},v_{5}),(v_{4},v_{6})\}$, $\mathcal M = \{v_{3}\}$, $\mathcal C(\mathcal M) = \{(v_{1},v_{2})\}$, $\mathcal T = \{v^{\ast },v^{1},v^{4}\}$, μ₁ = 15, $e_{\max \limits } = (v_{4},v_{5})$, and ${\varDelta }_{\mathcal M} = 5$.

Fig. 2

An instance to illustrate Part 1 of Case 1

Part 2.

If ${\varDelta }_{\mathcal M} > W(T_{e_{\max \limits }})$, we reduce all edges in $\mathcal C(\mathcal M)$ according to (2). Suppose there is an edge $e \in \mathcal C(\mathcal M)$ with $x(e)=\bar {x}(e)$. In this situation, both the 1-median and the 1-center parts are reduced. Thus, we have to update the set $\mathcal C$, $\mathcal M$ and $\mathcal C(\mathcal M)$ by applying the (BFS) approach on the subtree T_e. Also, we update the subtree $\mathcal T$ and the corresponding value μ₁ as some edges can not be further reduced. To summarize, we have to update $\mathcal C$, $\mathcal M$, $\mathcal C(\mathcal M)$, $\mathcal T$, μ₁, $e_{\max \limits }$, and ${\varDelta }_{\mathcal M}$. The complexity of this part is $O(|T_{e}|+|\mathcal C(\mathcal M)|)$ or linear time because both |T_e| and $|\mathcal C(\mathcal M)|$ are at most n.

For example, we consider Fig. 3 with α = 1 and $\mathcal C =\{(v_{1},v_{2}),(v_{1},v_{4})\}$. We can compute $e_{\max \limits } = \{(v_{1},v_{4})\}$ with $W(T_{e_{\max \limits }}) = 6$. As $\mathcal M =\{v_{3},v_{5}\}$ and $\mathcal C(\mathcal M) = \mathcal C$, we obtain ${\varDelta }_{\mathcal M} = 20/3 > W(T_{e_{\max \limits }})$. Thus, we reduce edges in $\mathcal C(\mathcal M)$. For $\bar {x}(v_{1},v_{2}) =\bar {x}(v_{1},v_{4}) = \bar {x}(v_{4},v_{5}) = \bar {x}(v_{4},v_{6}) = 1$, we simultaneously reduce (v₁,v₂) and (v₁,v₄) by 1 and 1/2. As $x(v_{1},v_{2}) = \bar {x}(v_{1},v_{2})$, we update $\mathcal C = \{(v_{1},v_{4}),(v_{2},v_{3})\}$, $\mathcal M = \{v_{3},v_{5}\}$, $\mathcal C(\mathcal M) = \{(v_{1},v_{4}), (v_{2},v_{3})\}$, $e_{\max \limits } = (v_{1},v_{4})$, and ${\varDelta }_{\mathcal M} = 14/3$.

Fig. 3

An instance to illustrate Part 2 of Case 1

Case 2. Where the Set $\mathcal M$ of Associated Vertices Changes

As the set $\mathcal M$ is related to the 1-center function, we assume in this case that all edges in $\mathcal C(\mathcal M)$ are reduced and we consider an edge e in the set.

Part 1

We investigate when the vertex v_e can change from one to another inside a subtree T_e. From the analysis in Nguyen [24], we know that v_e shifts to v if v is not in P(v_e,v^∗) and w(v) < w(v_e) while the modification of e is x^v(e) satisfying w(v_e)(d_ℓ(v^∗,v_e) − x^v(e)) = w(v)(d_ℓ(v^∗,v) − x^v(e)), that is,

$$ x^{v}(e) := \frac{w(v_{e})d_{\ell}(v^{\ast},v_{e})-w(v)d_{\ell}(v^{\ast},v)}{w(v_{e})-w(v)}. $$

For each vertex v ∈ V (T_e) such that v is either in P(v_e,v^∗) or w(v) ≥ w(v_e), we set $x^{v}(e) := +\infty$. Then, we denote by $x^{C}(e) := \min \limits _{v\in V(T_{e})}\{x^{v}(e)\}$ the minimum modification of e such that v_e changes. Furthermore, if we modify e by x^C(e), then we update $\mathcal M := (\mathcal M \backslash \{v_{e}\}) \cup \{v\}$ for a vertex v satisfying

$$ v := \arg\min\left\{w(v^{\prime}): v^{\prime} \in T_{e} \text{ and } w(v^{\prime})d_{\widetilde{\ell}}(v^{\prime},v^{\ast}) = \max_{v^{\prime\prime}\in V}w(v^{\prime\prime}) d_{\widetilde{\ell}}(v^{\prime\prime},v^{\ast})\right\} $$

and x^v(e) = x^C(e). To compute x^C(e) for e in $\mathcal C(\mathcal M)$, we have to compute x^v(e) for all v ∈ T_e in constant time. Hence, the complexity for computing x^C(e) is O(|T_e|) = O(n) time.

For example, say we reduce the edge (v₁,v₂) in Fig. 4, then $x^{v_{3}}((v_{1},v_{2})) = 2$ and $x^{v_{4}}((v_{1},v_{2})) = 6$. Thus, we derive x^C((v₁,v₂)) = 2. If we reduce the length of (v₁,v₂) by 2, the corresponding set $\mathcal M = \{v_{3}\}$.

Fig. 4

An instance to illustrate Part 1 of Case 2

Part 2

We investigate the cases where new vertices in $T \backslash \bigcup _{e \in \mathcal C(\mathcal M)}T_{e}$ are added to ${\mathscr{M}}$. Let $\mu _{2} := \max \limits \{w_{v_{e}}d_{\ell }(v_{e},v^{\ast }): e \in \mathcal C \backslash \mathcal C(\mathcal M)\}$ and $\mu := \max \limits \{\mu _{1},\mu _{2}\}$, where we know $\mu _{1} := \max \limits \{w_{v}d_{\ell }(v,v^{\ast }): v \in \mathcal T\}$ in the previous section. We observe that μ is not reduced for the reduction of edges in $\mathcal C(\mathcal M)$. In the case where we reduce all edges of $\mathcal C(\mathcal M)$, if an edge $e\in \mathcal C(\mathcal M)$ is reduced by x^M(e) satisfying w(v_e)(d(v^∗,v_e) − x^M(e)) = μ, that is,

$$ x^{M}(e) := \frac{w(v_{e})d(v^{\ast},v_{e}) - \mu}{w(v_{e})}, $$

then we get into one of the following two situations. If μ₁ < μ₂, there exists one or several new vertices v_e for $e \in \mathcal C \backslash \mathcal C(\mathcal M)$ that are added into $\mathcal M$ and the corresponding edges are added to $\mathcal C(M)$. If μ₁ ≥ μ₂, there exist a vertex u in $\mathcal T$ with $u := \arg \max \limits _{v\in V} w(v)d_{\widetilde {\ell }}(v,v^{\ast })$ in the modified tree T. As the 1-center part cannot be reduced any further from here on, the (RCPT) problem reduces to the reverse 1-median problem on the modified tree.

We consider Fig. 5 to illustrate this part for the case μ₁ < μ₂. For $\mathcal C = \{(v_{1},v_{2}),(v_{1},v_{4})\}$, we know that (v₁,v₂) in $\mathcal M$. We obtain μ = μ₂ = 18 and x^M(e) := 1. If we reduce (v₁,v₂) by 1, then $\mathcal M :=\{v_{3},v_{4}\}$.

Fig. 5

An instance to illustrate Part 2 of Case 2 with μ₁ < μ₂

In Fig. 6, we get μ₁ > μ₂. If we reduce (v₁,v₂) by 4, then

$$ w(v_{1})d(v_{1},v^{\ast}) = \max\limits_{v \in V}w(v)d_{\widetilde{\ell}}(v,v^{\ast}). $$

The 1-center part in the 1-centdian function can not be improved any further.

Fig. 6

An instance to illustrate Part 2 of Case 2 with μ₁ ≥ μ₂

We have already analyzed the two cases regarding the change of $\mathcal C$ or $\mathcal M$. Therefore, an edge e should be reduced by the minimum of the mentioned amounts in Case 1 and Case 2 as well as adapting to the budget constraint. Precisely, assuming we reduce the edges in $\mathcal C(\mathcal M)$ according to (1) subject to the budget constraint, that is, ${\sum }_{e \in \mathcal C(\mathcal M)}x(e) \leq B$, then by (2), $x(e) \leq \frac {1}{w(e){\sum }_{e^{\prime } \in \mathcal C(\mathcal M)}\frac {1}{w(v_{e^{\prime }})}}B$ must hold for each $e \in \mathcal C(\mathcal M)$. The following result states the minimum reduction of an edge e according to Proposition 2 such that the set $\mathcal C$ or $\mathcal M$ changes and the budget constraint holds.

Proposition 3

If ${\varDelta }_{\mathcal M} \leq W(T_{e_{\max \limits }})$, the minimum reduction of the edge $e_{\max \limits }$ such that the set $\mathcal C$ changes or the budget is fully used is

$$ \delta(e_{\max}) := \min\left\{\bar{x}(e_{\max}),B\right\}. $$

(5)

Otherwise, if ${\varDelta }_{\mathcal M} > W(T_{e_{\max \limits }})$, the minimum reduction of an edge e in $\mathcal C(\mathcal M)$ such that the set $\mathcal C$ or $\mathcal M$ changes or the budget is fully used, is

$$ \delta(e) := \min\left\{\bar{x}(e),x^{C}(e),x^{M}(e), \frac{1}{w(v_{e}){\sum}_{e^{\prime}\in \mathcal C(\mathcal M)}\frac{1}{w(v_{e^{\prime}})}}B\right\}. $$

(6)

Proof

Based on Proposition 2, we focus on reducing $e_{\max \limits }$ if ${\varDelta }_{\mathcal M} \leq W(T_{e_{\max \limits }})$. As maximum possible reduction of the edge $e_{\max \limits }$ is $\bar {x}(e_{\max \limits })$ and is bounded by the budget, we get the desired result. Otherwise, if ${\varDelta }_{\mathcal M} > W(T_{e_{\max \limits }})$, we reduce all edges in $\mathcal C(\mathcal M)$. Then, we get the result due to the analysis in Part 2 of Case 1 and the whole Case 2. □

By Proposition 3, we can identify the minimum reduction of an edge such that $\mathcal C$ or $\mathcal M$ changes. If ${\varDelta }_{\mathcal M} \leq W(T_{e_{\max \limits }})$, reducing the edge $e_{\max \limits }$ by $x(e_{\max \limits })=\delta (e_{\max \limits })$ yields the reduction of the 1-centdian function by $W(T_{e_{\max \limits }})\delta (e_{\max \limits })$. Otherwise, we can compute the minimum reduction of the 1-centdian function such that $\mathcal C$ or $\mathcal M$ changes based on (4) and Proposition 3.

Proposition 4

If we reduce all edges in $\mathcal C(\mathcal M)$, then the minimum reduction of the 1-centdian function which leads to the change of $\mathcal C$ or $\mathcal M$ is

$$ \kappa := \sum\limits_{e^{\prime} \in \mathcal C(\mathcal M)}\frac{1}{w(v_{e^{\prime}})}{\varDelta}_{\mathcal M}\min_{e\in \mathcal C(\mathcal M)}\{w(v_{e})\delta(e)\}. $$

(7)

Proof

By the formula for the reduction of the 1-centdian function given by (4) and the minimum reduction of an edge in $\mathcal {C}({\mathscr{M}})$ that leads to the change of $\mathcal C$ or $\mathcal M$ given by Proposition 3, we can trivially identify the minimum reduction of the 1-centdian function as in (7). □

Based on (7), we can trace back the reduction of each edge e in $\mathcal C(\mathcal M)$ by (2).

In the next page, we present a combinatorial algorithm for the (RCPT) problem. The idea of the algorithm is to reduce the length of the edge $e_{\max \limits }$ or all edges in $\mathcal C(\mathcal M)$ according to Proposition 3 and update necessary information in each iteration according to the analysis in Case 1 and Case 2. We repeat the iterations until the given budget is fully used. By Proposition 2, we know that the 1-centdian value is reduced as much as possible. Hence, we finally get the maximum reduction of the objective function after completing Algorithm 1.

Now, we analyze the complexity of the algorithm. We start with considering the number of iterations in the worst case scenario. For Case 1, after an edge is modified by its upper bound, it is not considered in future iterations. Therefore, there are at most O(n) iterations such that Case 1 occurs. For Part 1 of Case 2, we know that v_e for $e \in \mathcal C(\mathcal M)$ can be only shifted to its descendants inside the subtree T_e. Therefore, there are also at most O(n) iterations such that this part of Case 2 happens. Part 2 of Case 2 happens if there exist one or several edges in $\mathcal C \backslash \mathcal C(\mathcal M)$. Furthermore, if there is an edge e in $\mathcal C \backslash \mathcal C(\mathcal M)$ such that v_e is added into $\mathcal M$ in the current iteration, we later either reduce this edge by Case 1 or Part 1 of Case 2. In other words, we do not revisit the edge e again under Part 2 of Case 2 from the current iteration onwards. Therefore, the number of iterations such that Part 2 of Case 2 happens at most equals the number of edges in the tree, and thus there are linearly many such iterations. In the initialization step (lines 2–4), we can compute all related quantities in linear time as discussed in Section 3.1. In each iteration, we complete the computation as in Case 1 and Case 2 in linear time as discussed before. If the condition μ₁ = 𝜃 (line 29) holds, we apply the algorithm of Berman et al. [5] to solve the current instance in linear time. Therefore, the complexity of the algorithm is O(n²), where n is the number of vertices in T.

Theorem 2

The reverse centdian problem on trees can be solved in O(n²) time, where n is the number of vertices in the tree.

As an illustration of Algorithm 1, we provide the following example.

Example 1

Consider an instance of the reverse 1-centdian problem on a tree T in Fig. 7 with α = 2, $\bar {x}(v_{0},v_{1})=\bar {x}(v_{0},v_{2})=2$ and $\bar {x}(e)=1$ otherwise. Under the given budget B = 5, Algorithm 1 solves the corresponding problem in 5 iterations (see Table 1).

Fig. 7

An instance of the (RCPT) problem with α = 2

Table 1 Iterations of the (RCPT) by applying Algorithm 1

Therefore, the maximum improvement of the 1-centdian function within the budget B is $\mathcal R = 140$.

4 Conclusions

This paper addressed the uniform cost reverse 1-centdian problem on networks, where the 1-centdian function is a convex combination of the 1-median and the 1-center functions. We first proved that the problem is NP-hard by reducing it to the set cover problem. Specifically, we investigated the problem on trees and developed a greedy-like algorithm that solves the problem in quadratic time. To the best of our knowledge, this is the first work concerning the reverse centdian problem. Hence, the reverse centdian problem on other types of networks such as cycles, cactus, etc., is a promising research direction for the future. Another potential direction is to apply prediction models (see [21, 22]) to location theory in order to construct a focasting approach for the centdian problem on networks in both the classical and the inverse/reverse versions.