# Stability Radius and an Upgrading Model of Median Location on Trees

Van Huy Pham, Ngan Nguyen, Minh-Quang Cao, Hong-Phuong Dang, Thu-Le Tran

► To cite this version:

Van Huy Pham, Ngan Nguyen, Minh-Quang Cao, Hong-Phuong Dang, Thu-Le Tran. Stability Radius and an Upgrading Model of Median Location on Trees. Asia-Pacific Journal of Operational Research, 2025, 10.1142/s0217595925500307. hal-05111084

HAL Id: hal-05111084

https://hal.science/hal-05111084v1

Submitted on 13 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Stability Radius and an Upgrading Model of Median Location on Trees

Van Huy Pham¹, Ngan Nguyen², Minh-Quang Cao³,
Hong-Phuong Dang⁴, and Thu-Le Tran*²

¹Faculty of Information Technology, Ton Duc Thang University,
Ho Chi Minh, Vietnam

²Department of Mathematics, Teacher College, Cantho University,
Can Tho, Vietnam

³Nguyen Binh Khiem High School for the Gifted, Vinh Long,
Vietnam

⁴CentraleSupélec, IETR UMR CNRS 6164, Cesson-Sévigné, France

June 10, 2025

## Abstract

The single median facility location problem seeks to determine an optimal location to minimize the total weighted distance to existing demand points. However, in real-world scenarios, this optimal location can vary due to uncertainty of input data. In such situations, one can measure the robustness of the median location using stability radius, a concept in sensitivity analysis. In this paper, we first show that the stability radius of median location on tree admits a simple and tight lower bound. Furthermore, we investigate an upgrading model for this lower bound by adjusting vertex weights of the tree network within a specified budget. We also introduce a combinatorial approach capable of solving this problem efficiently.

**Keywords:** median location, stability radius, upgrading problem, tree

## 1 Introduction

Facility location problems on networks are fundamental in operations research, see e.g., Laporte *et al.* (2019) and Marianov and Eiselt (2024). Among these, the median location problem, which minimizes the total weighted distance to demand points, is one of the most well-known. The problem with *p* medians on

<footnote>*Corresponding author, ttle@ctu.edu.vn</footnote>
general networks was studied in Kariv and Hakimi (1979). A linear-time method for locating a single median on a tree was presented in Goldman (1971). For an efficient algorithm addressing the *p*-median problem on trees, refer to Tamir (1996).

An application of median location is the warehouse-to-lockers model in logistics, see e.g., Espejo and Marín (2023). Here, the warehouse is located at a median point of the network to minimize the total transportation cost to lockers at the network nodes. Each locker has a storage capacity to serve customer demands, and the transportation cost from the warehouse to each locker is proportional to both distance and storage capacity.

In practice, fluctuations of model parameters may cause instability in the optimality of established facilities, affecting the overall system's efficiency. The dependency of the optimal solution on the parameters is the subject of sensitivity analysis, see e.g., Goldengorin et al. (2006). Dynamic parameters in locations problems effecting the optimal solutions could include, e.g., node weights Erkut and Tansel (1992), node locations Cooper (1978), or both Drezner (1985).

In sensitivity analysis, the concept of the stability radius is well-considered. The stability radius measures the maximum level of noise added to the model parameters while ensuring that the solution remains optimal with respect to any noisy parameters within this noise level. The stability radius for binary programming problems has been studied in Chakravarti and Wagelmans (1998), showing that it can be evaluated in polynomial time if the optimization problem itself is polynomially solvable.

Although many studies have investigated sensitivity analysis for location problems, the stability radius has not been explored according to best of our knowledge. This paper aims to fill this gap by focusing on median locations. Given that the definition of the stability radius is difficult to work with, we propose a lower bound for the stability radius. This lower bound is simple and tight, meaning it equals the stability radius under mild conditions. Loosely speaking, this lower bound serves as a good approximation for the true stability radius.

Beyond the study of stability radius, we also investigate in this paper the problem of enhancing the robustness of median location. Let us consider the warehouse-to-locker model as motivation. Recall that the changes in storage levels to accommodate unknown varying demands may lead to instability in warehouse optimality and logistics efficiency. To enhance the robustness of the system, we study the problem of adjusting storage levels to maximize the stability radius's lower bound of the warehouse. We refer to this problem as the "Upgrading stability radius (USR) of median point".

The proposed USR problem is closely related to inverse, reverse, and upgrading/downgrading problems, all of which fall under the class of network modification problems focusing on facility locations. In inverse problems, model parameters are altered to make a prespecified non-optimal location optimal. Some inverse models for median locations were extensively studied in, e.g., Burkard et al. (2008); Guan and Zhang (2012); Nguyen (2016a). It has also been investigated for other locations, e.g., center locations Alizadeh and Burkard (2011);
Nguyen et al. (2019), ordered median Nguyen and Chassein (2015), and sta- ble points Pham et al. (2021). Reverse problems involve changing parameters to optimize an objective of some feasible solution, with studies focusing on median locations Nhan et al. (2023), center locations Nguyen (2016b); Toan et al. (2024), and selective locations Etemad and Alizadeh (2018). In upgrading (downgrading) problems, the objective is to adjust network parameters within bounds to optimize the objective value of the modified network. Research in this area focuses on median locations Gassner (2008); Sepasian and Rahbarnia (2015); Plastria (2016), center location Sepasian (2018), hub location Blanco and Marín (2019), obnoxious median Afrashteh et al. (2020), and maximal cov- ering Baldomero-Naranjo et al. (2022).

Regarding USR problem, we formulate it as a linear programming problem and propose an efficient combinatorial approach to solve it. Our approach in- volves several simple transformations to simplify the problem. One important transformation is to exchange the objective function and budget constraint. We refer to the transformed problem as the “parametric version of USR”. This transformation allows the new problem to be solved in closed form and enables an efficient recovery of the previous problem’s solution.

The paper is organized as follows. In Section 2, we revisit the median location on tree networks and its optimality condition. In Section 3, we discuss the stability radius of the median point and propose a simple and tight lower bound. In Section 4, we introduce the upgrading problem for stability radius’s lower bound of median location and propose an efficient combinatorial algorithm to solve it.

## 2 Preliminaries

**Notations.** Beyond the graph notations, we also use some vector notations. Specifically, we denote the space of vectors with nonnegative entries by $\mathbb{R}_+^n$. We denote the L1 norm and max norm by $\| \cdot \|_1$ and $\| \cdot \|_\infty$, respectively. The inner product of two vectors is denoted by $\langle \cdot, \cdot \rangle$. For $w \in \mathbb{R}^n$ and $\varepsilon \in \mathbb{R}$, we denote by $[w - \varepsilon, w + \varepsilon]$ the hypercube in $\mathbb{R}^n$ centered at $w$ with half edge length $\varepsilon$. For a real number $\alpha$, we define $[\alpha]_+ = \max(0, \alpha)$.

We now recall the notion of a median point on a tree network and its opti- mality condition.

Let $T = (V, E)$ be a tree network with vertex set $V = \{v_1, ..., v_n\}$ and edge set $E$. Each vertex $v_i \in V$ has a nonnegative weight $w_i$. We denote by $w = (w_1, ..., w_n) \in \mathbb{R}_+^n$ the nonnegative weight vector. For the original vector $w$, we assume that

$$ \sum_{i=1}^{n} w_i = 1. \qquad (1) $$

We associate each edge $e \in E$ with a nonnegative length $\ell_e$. The distance between two vertices $u$ and $v$, denoted by $d(u, v)$, is the sum of the edge lengths on the unique path connecting $u$ and $v$.
We say that a point $x$ belongs to a tree $T$ if it is either a vertex or lies on the interior of some edge of $T$, denoted as $x \in T$. Any such point can be treated as a vertex with zero weight, splitting the edge into two smaller edges. With this interpretation, $T$ can be viewed as a continuous set, where the distance between any two points on the tree is defined analogously to the distance between two vertices, see e.g., (Dearing et al., 1976, Section 2).

For each weight vector $w \in \mathbb{R}_+^n$, the median function associated with $w$ is defined as

$$f_w(x) = \sum_{i=1}^{n} w_i d(x, v_i).$$

for $x \in T$. On each path of the tree, the convexity of the distance implies the convexity of the median function $f_w$. For more details on path convexity on tree graphs, see (Dearing et al., 1976, Lemma 2).

The problem of finding a point $x \in T$ minimizing median function is called median problem. We call the set of minimizers the median set and denote it by $X_w^*$. Each element in $X_w^*$ is called a median point associated with $\tilde{w}$. In general, $X_w^*$ is a subtree of $T$. When all weights $w_i$ are strictly positive, then $X_w^*$ become a single vertex or an edge of $T$.

Let $T$ be rooted at $v_1 \in T$ and let $N(v_1)$ be the set of neighbourhood vertices of $v_1$. Specifically, if $v_1$ lies in the interior of an edge $(u, v)$, then $N(v_1) = \{u, v\}$. Let $\mathbb{1}_{T'} \in \mathbb{R}^n$ be the characteristic vector of subtree $T' \subset T$, i.e., its $i$th entry equals to 1 if $v_i \in T'$, and equals to 0 otherwise. By this notation, the total weight of subtree $T'$ is $\langle w, \mathbb{1}_{T'} \rangle$. Let $T_u$ be the maximal connected subtree rooted at $u \in N(v_1)$ that does not include $v_1$.

The next lemma provides a characterization of when median set is a subset of $T_u$.

**Lemma 2.1.** For any $u \in N(v_1)$, $X_w^*$ is a subset of $T_u$ if and only if the total weight of $T_u$ is strictly larger than its complement, i.e.,

$$\langle w, \mathbb{1}_{T_u} \rangle > \langle w, \mathbb{1}_{T \setminus T_u} \rangle \iff X_w^* \subset T_u. \quad (2)$$

*Proof.* Instead of proving (2), we can prove its equivalent statement:

$$\langle w, \mathbb{1}_{T_u} \rangle \le \langle w, \mathbb{1}_{T \setminus T_u} \rangle \iff X_w^* \not\subset T_u. \quad (3)$$

The proof for the forward direction can be found in the seminal paper of Goldman (Goldman, 1971, Lemma 1).

We now prove the converse direction. Assuming that $X_w^* \not\subset T_u$. Then, there exists some vertex median, say $m$, belonging to $T \setminus T_u$. Notice that $v_1$ belongs to the path connecting $m$ and $u$. On this path, the convexity of median function and the optimality of $m$ implies that $f_w(v_1) \le f_w(u)$. Therefore,

$$0 \ge f_w(v_1) - f_w(u) = (\langle w, \mathbb{1}_{T_u} \rangle - \langle w, \mathbb{1}_{T \setminus T_u} \rangle)d(v_1, u). \quad (4)$$

We thus obtain $\langle w, \mathbb{1}_{T \setminus T_u} \rangle \ge \langle w, \mathbb{1}_{T_u} \rangle$. The proof is completed. $\square$
The following well-known theorem, which is derived from Lemma 2.1, provides a necessary and sufficient condition for a point to be a median.

**Theorem 2.1.** A point $v_1$ is a median point on tree T w.r.t. weight vector $w \in \mathbb{R}_+^n$ if and only if

$$ \langle w, \mathbb{1}_{T_u} \rangle \le \langle w, \mathbb{1}_{T \setminus T_u} \rangle, \quad \forall u \in N(v_1). \quad (5) $$

It is also essential to notice an equivalent version (5) written as:

$$ \langle w, \mathbb{1}_{T_u} \rangle \le \frac{1}{2}, \quad \forall u \in N(v_1). \quad (6) $$

This means $v_1$ is a median point if the total weight of each branch rooted at every neighbor of $v_1$ is at most half the total weight of the tree. The median point is not unique and depends only on vertex weights, not edge lengths.

**Example 2.1.** Let T be a weighted tree defined in Fig. 1. In this case, $v_1$ is a median point since $\langle w, \mathbb{1}_{T_{v_2}} \rangle = 0.33$, $\langle w, \mathbb{1}_{T_{v_3}} \rangle = 0.12$, $\langle w, \mathbb{1}_{T_{v_4}} \rangle = 0.45$ all less than $\frac{1}{2}$.

<figure><img src="image_2.png" /><figcaption>Figure 1: A weighted tree with median $v_1$ according to Theorem 2.1</figcaption></figure>

# 3 Stability radius of median location

Let $w \in \mathbb{R}_+^n$ be a weight vector satisfying unit mass constraint (1) and $v_1$ be a median point associated with $w$.

In practice, the weight vector $w$ can be perturbed to some new vector $\tilde{w} \in \mathbb{R}_+^n$. We assume that the difference between $w$ and $\tilde{w}$ is small, i.e., $\|\tilde{w}-w\|_{\infty} \le \varepsilon$, or equivalently, $\tilde{w} \in [w-\varepsilon, w+\varepsilon]$ for some small perturbation level $\varepsilon > 0$. In this setting, we aim to investigate the stability of the median point $v_1$. Specifically, we are interested in the largest possible level $\varepsilon$ such that $v_1$ remains optimal corresponding to $\tilde{w}$, i.e.,

$$ R(w) = \sup\{\varepsilon \ge 0 : v_1 \in X_{\tilde{w}}^*, \quad \forall \tilde{w} \in [w-\varepsilon, w+\varepsilon] \cap \mathbb{R}_+^n \}. $$

We call, by definition, $R(w)$ the stability radius of median point $v_1$ with weights $w$. Despite the implicit definition of $R(w)$, it has a simple but tight lower bound.
**Theorem 3.1.** We have

$$R(w) \geq \underline{R}(w) := \min_{u \in N(v_1)} \frac{1}{n} (1 - 2\langle w, \mathbb{1}_{T_u} \rangle). \quad (7)$$

Furthermore, the equality in (7) holds if $\underline{R}(w) < \min_{i=1,...,n} w_i$.

*Proof.* Let $\varepsilon_u = \frac{1}{n}(1 - 2\langle w, \mathbb{1}_{T_u} \rangle)$. By elementary computations, we can verify that

$$\langle w + \varepsilon_u, \mathbb{1}_{T_u} \rangle = \langle w - \varepsilon_u, \mathbb{1}_{T \setminus T_u} \rangle.$$

To prove (7), it is sufficient to show that for any $\varepsilon$ such that $\varepsilon \leq \min_{u \in N(v_1)} \varepsilon_u$, then $v_1$ is a median point w.r.t. any $\tilde{w} \in [w - \varepsilon, w + \varepsilon] \cap \mathbb{R}_+^n$. For all $\varepsilon \leq \min_{u \in N(v_1)} \varepsilon_u$, $\tilde{w} \in [w - \varepsilon, w + \varepsilon] \cap \mathbb{R}_+^n$ and $u \in N(v_1)$, we have

$$\langle \tilde{w}, \mathbb{1}_{T_u} \rangle \leq \langle w + \varepsilon_u, \mathbb{1}_{T_u} \rangle = \langle w - \varepsilon_u, \mathbb{1}_{T \setminus T_u} \rangle \leq \langle \tilde{w}, \mathbb{1}_{T \setminus T_u} \rangle. \quad (8)$$

By Theorem 2.1, one concludes that $v_1 \in X_{\tilde{w}}^*$.

Assuming that $\underline{R}(w) < \min_{i=1,...,n} w_i$, we aim to prove that $R(w) = \underline{R}(w)$. To this end, we show that for noise level $\varepsilon$ strictly larger than $\underline{R}(w)$, then there exists some noisy feasible weight $\tilde{w}$ such that $v_1$ is no longer optimal w.r.t. $\tilde{w}$. Specifically, let $\varepsilon \in (\underline{R}(w), \min_{i=1,...,n} w_i]$, we then construct some $\tilde{w} \in [w - \varepsilon, w + \varepsilon] \cap \mathbb{R}_+^n$ so that $v_1 \notin X_{\tilde{w}}^*$. Since $\varepsilon > \underline{R}(w)$, there exists some $u \in N(v_1)$ such that $\varepsilon > \varepsilon_u$. Therefore,

$$\langle w + \varepsilon, \mathbb{1}_{T_u} \rangle > \langle w + \varepsilon_u, \mathbb{1}_{T_u} \rangle = \langle w - \varepsilon_u, \mathbb{1}_{T \setminus T_u} \rangle > \langle w - \varepsilon, \mathbb{1}_{T \setminus T_u} \rangle. \quad (9)$$

Let us define $\tilde{w} = (w+\varepsilon) \odot \mathbb{1}_{T_u} + (w-\varepsilon) \odot \mathbb{1}_{T \setminus T_u}$ where $\odot$ denotes the Hadamard product between two vectors. Note that $\tilde{w} \in [w - \varepsilon, w + \varepsilon]$ is positive since $\varepsilon \leq \min_{i=1,...,n} w_i$. Observe that (9) can be rewritten as $\langle \tilde{w}, \mathbb{1}_{T_u} \rangle > \langle \tilde{w}, \mathbb{1}_{T \setminus T_u} \rangle$. Thus, $X_{\tilde{w}}^* \subset T_u$ due to Lemma 2.1. Since $v_1 \notin T_u$, we have $v_1 \notin X_{\tilde{w}}^*$. This completes the proof.

□

In Theorem 3.1, the lower bound $\underline{R}(w)$ is guaranteed to be nonnegative due to the optimality of $v_1$ (6). Furthermore, the condition $\underline{R}(w) < \min_{i=1,...,n} w_i$ is equivalent to the fact that any weight in the range $[w - \underline{R}(w), w + \underline{R}(w)]$ is strictly positive, making it a mild condition. This condition holds when, for example, $w_i = \frac{1}{n}$ for all $i = 1, ..., n$.

**Example 3.1.** Consider the weighted tree T in Fig. 1. The stability radius $R(w) = \underline{R}(w) = \min\{\varepsilon_{v_2}, \varepsilon_{v_3}, \varepsilon_{v_4}\} = \frac{0.1}{9}$ where $\varepsilon_{v_2} = \frac{0.34}{9}$, $\varepsilon_{v_3} = \frac{0.76}{9}$, $\varepsilon_{v_4} = \frac{0.1}{9}$.

# 4 Upgrading stability radius's lower bound for median location

In this section, we first introduce an upgrading model in Section 4.1. Next, we propose its parametric versions and establish their relationships in Section 4.2. Finally, we show that the parametric problem can be solved in a closed form in Section 4.3, which yields an efficient combinatorial approach for solving the target problem in Section 4.4.
## 4.1 Formulations

In this section, we aim to enhance the stability of median location. Due to the intricate nature of stability radius $R(\cdot)$, we focus instead on upgrading its lower bound $\underline{R}(\cdot)$.

Let $v_1 \in V$ be a median point associated with $w \in \mathbb{R}_+^n$ satisfying unit mass constraint (1). Given a budget $B \ge 0$, our goal is to modify the weights from $w$ to some $\tilde{w} \in \mathbb{R}_+^n$ within this budget, while ensuring that $v_1$ remains a median, with the objective of maximizing $\underline{R}(\tilde{w})$. Here, we assume that the cost of modifying weights from $w$ to $\tilde{w}$ is measured by L1-norm, i.e., $\|\tilde{w} - w\|_1$. Furthermore, we assume that the total weights is unchanged, i.e., $\sum_{i=1}^n \tilde{w}_i = 1$ and not deviate too much from $w$, i.e., $\tilde{w} \in [w - \varepsilon_0, w + \varepsilon_0]$, for some $\varepsilon_0 \in [0, \min_{i=1,...,n} w_i]$. We refer to this problem as upgrading stability radius (USR) of median point $v_1$ and input data $w$.

Specifically, the mathematical model for our USR problem can be written as follows:

$$ \max \underline{R}(\tilde{w}) \qquad (\text{USR-10}) $$

$$ \text{s.t.} \quad \|\tilde{w} - w\|_1 \le B \qquad (\text{USR-10a}) $$

$$ v_1 \text{ is median w.r.t. } \tilde{w} \qquad (\text{USR-10b}) $$

$$ \sum_{i=1}^{n} \tilde{w}_i = 1 \qquad (\text{USR-10c}) $$

$$ \|\tilde{w} - w\|_{\infty} \le \varepsilon_0 \qquad (\text{USR-10d}) $$

In the remaining of this subsection, our goal is to simplify USR problem by: 1) rewriting the maximum problem (USR-12) as a minimum problem; 2) eliminating the median constraint (USR-10b); and 3) changing the variable from weight vector $\tilde{w}$ to modification vector $x = \tilde{w} - w$.

By Theorem 3.1, the problem of maximizing $\underline{R}(\tilde{w})$ can be rewritten as a minimizing problem:

$$ \max_{\tilde{w}} \underline{R}(\tilde{w}) = \max_{\tilde{w}} \min_{u \in N(v_1)} \frac{1}{n}(1 - 2\langle \tilde{w}, \mathbb{1}_{T_u} \rangle) = \frac{1}{n} - \frac{2}{n} \min_{\tilde{w}} \max_{u \in N(v_1)} \langle \tilde{w}, \mathbb{1}_{T_u} \rangle. \quad (11) $$

Next, let $w^*$ be an optimal weight vector of (USR-10), then it is clear that

$$ \max_{u \in N(v_1)} \langle w^*, \mathbb{1}_{T_u} \rangle \le \max_{u \in N(v_1)} \langle w, \mathbb{1}_{T_u} \rangle \le \frac{1}{2}. $$

This observation implies the optimality of $v_1$ w.r.t. $w^*$. Therefore, the constraint (USR-10b) is redundant and can be removed.

Finally, let $x = \tilde{w} - w$ be the vector of modifications. By this change of variable, the redundancy of constraint (USR-10b) and the reformulation of
objective function (11), the problem (USR-10) can be rewritten as follows:

$$ \min \quad \max_{u \in N(v_1)} \langle w + x, 1_{T_u} \rangle \qquad (\text{USR-12}) $$

$$ \text{s.t.} \quad \|x\|_1 \le B \qquad (\text{USR-12a}) $$

$$ \sum_{i=1}^{n} x_i = 0 \qquad (\text{USR-12b}) $$

$$ x_i \in [-\epsilon_0, \epsilon_0], \quad \forall i = 1, \dots, n \qquad (\text{USR-12c}) $$

In the remaining of this paper, we will focus on (USR-12) instead of (USR-10). The problem (USR-12) is a linear program, which can be solved using simplex method, or polynomial-time algorithms Karmarkar (1984); Megiddo (1984). However, these methods can be slow in high dimension. In the next subsection, we propose a more efficient combinatorial method to solve the problem (USR-12) by leveraging its specific structure.

## 4.2 Parametric version of upgrading stability radius problem

Now, let us fix some $t \ge 0$ and compute the minimum budget of modifications to achieve a cost not greater than $t$:

$$ \min \quad \|x\|_1 \qquad (\text{PUSR-13}) $$

$$ \text{s.t.} \quad \max_{u \in N(v_1)} \langle w + x, 1_{T_u} \rangle \le t \qquad (\text{PUSR-13a}) $$

$$ \sum_{i=1}^{n} x_i = 0 \qquad (\text{PUSR-13b}) $$

$$ x_i \in [-\epsilon_0, +\epsilon_0], \quad \forall i = 1, \dots, n \qquad (\text{PUSR-13c}) $$

We refer to this new problem as the “parametric version of upgrading stability radius” (PUSR) problem. At first glance, the new problem (PUSR-13) is obtained from (USR-12) by swapping the objective and the budget constraint. Throughout the remainder of the paper, readers will find that: 1) solving the new problem is simpler, and 2) there is a straightforward transformation between the solutions of the two problems.

For fixed budget $B$, let $x^*, t^*$ denote an optimal solution and minimum objective value of (USR-12), respectively. For each $t$, let $\hat{x}(t)$, $\beta(t)$ be an optimal solution and the minimum budget corresponding to (PUSR-13). Note that $\beta(\cdot)$ is a nondecreasing function on its domain and equal to $+\infty$ if the feasible set of (PUSR-13) is empty.

The relationship between $(t, \beta(t))$ and $(t^*, B)$ is established as follows.

**Lemma 4.1.** $\beta(t) \le B$ if and only if $t \ge t^*$.

*Proof.* Let $P(x) = \max_{u \in N(v_1)} \langle w + x, 1_{T_u} \rangle$. If $\beta(t) \le B$, then $\hat{x}(t)$ is feasible w.r.t. to (USR-12), thus, $P(\hat{x}(t)) \ge P(x^*)$. Therefore, $t \ge P(\hat{x}(t)) \ge P(x^*) =$
$t^*$ where the first inequality follows from (PUSR-13a). We now prove the converse. Assuming that $t \ge t^*$. Since $t^* = P(x^*)$, we have $P(x^*) \le t$. This yields the feasibility of $x^*$ w.r.t. (PUSR-13). Therefore, $\|\hat{x}(t)\|_1 \le \|x^*\|_1$. The feasibility of $x^*$ w.r.t. (USR-12) implies $\|x^*\|_1 \le B$. Hence, $\beta(t) = \|\hat{x}(t)\|_1 \le B$. This concludes the proof. □

From Lemma 4.1, it is important to notice that

$$ \beta(t^*) \le B. \qquad (14) $$

In the following, we derive a “transformation” from $(\hat{x}(t), \beta(t))$ to $(x^*, t^*)$.

**Proposition 4.1.** The optimal objective value $t^*$ of (USR-12) satisfies

$$ t^* = \inf\{t : \beta(t) \le B\}. \qquad (15) $$

and $\hat{x}(t^*)$ is an optimal solution of (USR-12).

*Proof.* From Lemma 4.1, we can see that $t^* \le \inf\{t : \beta(t) \le B\}$. If $t^* < \inf\{t : \beta(t) \le B\}$, then it is clear that $\beta(t^*) > B$, this contradicts to (14). Therefore, $t^* = \inf\{t : \beta(t) \le B\}$.

From (14), we know that $\hat{x}(t^*)$ is feasible to (USR-12), thus $P(\hat{x}(t^*)) \ge P(x^*) = t^*$. Furthermore, the feasibility of $\hat{x}(t^*)$ corresponding to (PUSR-13a) implies that $t^* \ge P(\hat{x}(t^*))$. Combining these facts yields the optimality of $\hat{x}(t^*)$ w.r.t. (USR-12). □

From Proposition 4.1, one can see that if one can solve (PUSR-13), i.e., knowing $\beta(t)$ and $\hat{x}(t)$ for any $t$, then one can construct an optimal solution $x^*$ of (USR-12), by choosing $x^* = \hat{x}(t^*)$, where $t^*$ is computed by (15).

Before solving (PUSR-13) in the next subsection, we propose a change of variable to reduce its dimension. Note that there exists an optimal solution where the entries in each subtree $T_u$, $u \in N(v_1)$, are equal. Therefore, we may introduce new variables, each representing the sum of $x_i$ for $v_i$ belonging to each $T_u$.

Let $N(v_1) = \{u_1, \dots, u_k\}$, $u_0 = v_1$ and $T_{u_0} = \{v_1\}$. Denote by $\gamma_j = \langle w, \mathbb{1}_{T_{u_j}} \rangle$ the total weight of subtree $T_{u_j}$ for $j = 0, 1, \dots, k$. For $x \in \mathbb{R}^n$, define a new vectors $z, \bar{z} \in \mathbb{R}^{k+1}$ with $j$th entry, $j = 0, 1, \dots, k$, as follows:

$$ z_j = \langle x, \mathbb{1}_{T_{u_j}} \rangle, $$

$$ \bar{z}_j = \varepsilon_0 |T_{u_j}|. $$

By this change of variable, instead of considering problem (PUSR-13), one can focus on the following problem with smaller dimension by keeping all the
constraints, but replacing the objective $||x||_1$ by its lower bound $||z||_1$:

$$ \min \sum_{j=0}^{k} |z_j| \qquad (\text{PUSR-16}) $$

$$ \text{s.t.} \quad \max_{j=1,...,k} (\gamma_j + z_j) \le t \qquad (\text{PUSR-16a}) $$

$$ \sum_{j=0}^{k} z_j = 0 \qquad (\text{PUSR-16b}) $$

$$ z_j \in [-\bar{z}_j, \bar{z}_j], \quad \forall j = 0, 1, ..., k \qquad (\text{PUSR-16c}) $$

The following result asserts that by solving (PUSR-16), one can retrieve the solution of (PUSR-13) while maintaining the same objective value.

**Proposition 4.2.** The problem (PUSR-13) and (PUSR-16) have the same minimum objective value $\beta(t)$. Furthermore, let $\hat{z}(t)$ be the solution w.r.t. (PUSR-16). Then an optimal solution $\hat{x}(t)$ for (PUSR-13) is given by

$$ \hat{x}_i(t) = \frac{\hat{z}_j(t)}{|T_{u_j}|}, \quad \forall v_i \in T_{u_j}, \forall j = 0, 1, ..., k. \qquad (17) $$

The proof of (PUSR-16) is omitted for simplicity.

We conclude this subsection with a characterization of the nonemptyness of the feasibility set of (PUSR-16). Let

$$ J^{\le}(t) = \{j \in \{1, ..., k\} : \gamma_j \le t\} $$

$$ J^{>}(t) = \{j \in \{1, ..., k\} : \gamma_j > t\} $$

**Proposition 4.3.** The feasible set of (PUSR-16) is nonempty iff

$$ \bar{z}_0 + \sum_{j \in J^{\le}(t)} \min(\bar{z}_j, t - \gamma_j) \ge \sum_{i \in J^{>}(t)} (\gamma_i - t). \qquad (18) $$

*Proof.* If the feasible set of (PUSR-16) is nonempty, then there exists some feasible solution $z \in \mathbb{R}^{k+1}$ satisfies the constraint (PUSR-16b), i.e.,

$$ z_0 + \sum_{j \in J^{\le}(t)} z_j = - \sum_{j \in J^{>}(t)} z_j. \qquad (19) $$

From the feasibility of $z$, it is not hard to verify that the LHS of (19) is upper bounded by the LHS of (18) and the RHS of (19) is lower bounded by the RHS of (18). We therefore obtain (18). Conversely, assuming that (18) does not hold. By the same estimations, one obtains

$$ z_0 + \sum_{j \in J^{\le}(t)} z_j < - \sum_{j \in J^{>}(t)} z_j. $$

This violates the constraint (PUSR-16b) and, thus, the feasible set is empty. □
## 4.3 Solution approach for the parametric version of upgrading stability radius problem

Now, we demonstrate that the simplified parametric problem (PUSR-16) admits an optimal solution $\hat{z}(t)$ and the optimal objective $\beta(t)$ with closed-form expression. Let us define $\hat{z}(t)$ according to two cases. If $\bar{z}_0 \ge \sum_{i=1}^k [\gamma_i - t]_+$, we choose

$$ 
\begin{align} 
\hat{z}_j(t) &= -(\gamma_j - t), & j \in J^>(t) \nonumber \\
\hat{z}_j(t) &= 0, & j \in J^\leq(t) \nonumber \\
\hat{z}_0(t) &= \sum_{j \in J^>} (\gamma_j - t). \tag{20}
\end{align} 
$$

Otherwise,

$$ 
\begin{align} 
\hat{z}_j(t) &= -(\gamma_j - t), & j \in J^>(t) \nonumber \\
\hat{z}_j(t) &= \min(\bar{z}_j, \underline{t} - \gamma_j), & j \in J^\leq(t) \tag{21} \\
\hat{z}_0(t) &= \bar{z}_0, \nonumber
\end{align} 
$$

where $\underline{t}$ is such that

$$ \bar{z}_0 + \sum_{j \in J^\leq(t)} \min(\bar{z}_j, \underline{t} - \gamma_j) = \sum_{i \in J^>(t)} (\gamma_i - t). \tag{22} $$

The following theorem provides closed-form expression for $\beta(t)$ and asserts the optimality of $\hat{z}(t)$.

**Proposition 4.4.** If the optimal objective $\beta(t)$ is finite, then

$$ \beta(t) = 2 \sum_{i=1}^{k} [\gamma_i - t]_+, \tag{23} $$

where $[\alpha]_+ = \max(0, \alpha)$ for $\alpha \in \mathbb{R}$. Furthermore, $\hat{z}(t)$ defined by (20) and (21) is an optimal solution for (PUSR-16).

*Proof.* We split the proof into two steps. In the first step, we show that $2 \sum_{i=1}^k [\gamma_i - t]_+$ is a lower bound for the objective of (PUSR-16), i.e., $\beta(t) \ge 2 \sum_{i=1}^k [\gamma_i - t]_+$. In the second step, we show that $2 \sum_{i=1}^k [\gamma_i - t]_+$ is actually the minimum value of (PUSR-16) by demonstrating that $\hat{z}(t)$, defined in either (20) or (21), satisfies $\|\hat{z}(t)\|_1 = 2 \sum_{i=1}^k [\gamma_i - t]_+$.

**Step 1.** Intuitively, for some given $t$, one needs to reduce $\gamma_j$ for $i \in J^>(t)$ and, therefore, have to increase $\gamma_j$ for $j \in J^>(t)$ to maintain equation (PUSR-16b). In other words, $z_j$ should be nonpositive for $j \in J^>(t)$ and should be nonnegative for $j \in J^\leq(t)$. This intuition motivates the following tricky estimations to obtain a tight lower bound for the objective function:

$$ \|z\|_1 = \sum_{j=0}^{k} |z_j| = |z_0| + \sum_{i \in J^\leq(t)} |z_i| + \sum_{i \in J^>(t)} |z_i| \ge z_0 + \sum_{i \in J^\leq(t)} z_j - \sum_{i \in J^>(t)} z_j. $$
By (PUSR-16b), one has $z_0 + \sum_{i \in J \le (t)} z_j = - \sum_{i \in J > (t)} z_j$. Thus,

$$ \|z\|_1 \ge -2 \sum_{i \in J > (t)} z_j. $$

Notice that for $j \in J > (t)$, we have $-z_j \ge \gamma_j - t > 0$, thus,

$$ \|z\|_1 \ge 2 \sum_{j \in J > (t)} (\gamma_j - t) = 2 \sum_{j=1}^{k} [\gamma_j - t]_+. $$

From this estimation, one concludes that $2 \sum_{i \in J > (t)} (\gamma_i - t)$ is a lower bound for the objective value in problem (PUSR-16).

**Step 2.** We now show that there exists some feasible vector $z$ of problem (PUSR-16) so that

$$ \|z\|_1 = 2 \sum_{i \in J > (t)} (\gamma_i - t). \qquad (24) $$

That vector $z$ can be defined as follows. For the index set $J > (t)$, we set

$$ z_j = -(\gamma_j - t), \quad \forall j \in J > (t). $$

For $j \in \{0\} \cup J^{\le}(t)$, we aim at choosing $z_j$ as nonnegative numbers so that the sum equal to $\sum_{i \in J > (t)} (\gamma_i - t)$. To this end, let us consider two cases. If $\bar{z}_0 \ge \sum_{i \in J > (t)} (\gamma_i - t)$, then one can simply set

$$ \begin{aligned} z_0 &= \sum_{i \in J > (t)} (\gamma_i - t), \\ z_j &= 0, \quad \forall j \in J^{\le}(t). \end{aligned} $$

Otherwise, we have $\bar{z}_0 < \sum_{i \in J > (t)} (\gamma_i - t)$. In this case, one sets

$$ \begin{aligned} z_0 &= \bar{z}_0, \\ z_j &= \min(\bar{z}_j, \underline{t} - \gamma_j), \quad \forall j \in J^{\le}(t), \end{aligned} $$

where $\underline{t}$ is defined in (22).

We now show the existence of $\underline{t}$. Let $\varphi$ denote the function $\underline{t} \mapsto \bar{z}_0 + \sum_{j \in J^{\le}(t)} \min(\bar{z}_j, \underline{t} - \gamma_j)$. We observe that $\varphi(0) \le \bar{z}_0 < \sum_{i \in J > (t)} (\gamma_i - t)$ and $\varphi(t) \ge \sum_{i \in J > (t)} (\gamma_i - t)$ due to Proposition 4.3. The continuity of $\varphi$ therefore implies the existence of $\underline{t}$ satisfying (22). Finally, it is not hard to verify that $z$ is a feasible solution of (PUSR-16) and satisfies (24). By choosing $\hat{z}(t) = z$, we complete the proof. $\square$

We now analyse the complexity of solving (PUSR-16). The main complexity is finding $\underline{t}$. For fixed $t$, one can find $\underline{t}$ in (22) using binary search in $O(\log k)$ steps since the function $\underline{t} \mapsto \bar{z}_0 + \sum_{j \in J^{\le}(t)} \min(\bar{z}_j, \underline{t} - \gamma_j)$ is nondecreasing and piecewise linear with $O(k)$ breakpoints. Note that the evaluation of this function costs $O(k)$. Therefore, the problem (PUSR-16) can be solved in $O(k \log k)$.

Since the transformation (17) costs $O(n)$, the problem (PUSR-13) can be solved in $O(n + k \log k)$.
## 4.4 Solution approach for the upgrading stability radius problem

We now describe a combinatorial approach for finding an optimal solution $w^*$ of the original upgrading stability radius problem (USR-10) by the transformations developed in previous subsections.

We have $w^* = w + x^*$ where $x^*$ is some optimal solution of (USR-12). By Proposition 4.1, we can choose $x^* = \hat{x}(t^*)$. Note that one can construct $\hat{x}(t)$ from $\hat{z}(t)$ for any $t$ by using Proposition 4.2, equation (17) and the expression of $\hat{z}(t)$ given by (20) or (21). Regarding the value $t^*$, it can be found in $O(k \log k)$ where $k$ is the degree of $v_1$ using binary search since $t^* = \inf\{t \ge 0 : \beta(t) \le B\}$ and the function $\beta(\cdot)$ determined in Proposition 4.4 is piecewise linear and nonincreasing. Refer to Fig. 2 for an overview of the transformations between problems and solutions.

<figure><img src="image_3.png" /><figcaption>Figure 2: Transformations of four upgrading problems. Each box contains a problem and its optimal solution. Each arrow stands for the transformation between the problems along with main results connecting them.</figcaption></figure>

Recall that solving (PUSR-13) costs $O(n + k \log k)$ and finding $t^*$ can be done in $O(k \log k)$, the overall complexity of solving problem (USR-10) is $O(n + k \log k)$.

**Theorem 4.1.** *The problem of upgrading stability radius's lower bound (USR-10) for median point on tree networks (USR-10) can be solved in $O(n + k \log k)$ time where $n$ is the number of vertices of tree and $k$ is the degree of median point $v_1$.*

Finally, we conclude this section by an example demonstrating the main steps in solving (USR-10).

**Example 4.1.** *Consider problem (USR-12) with budget $B = 0.36$, noise level $\epsilon_0 = 0.05$ and the weighted tree in Fig. 1. Let $u_0 = v_1$, $u_1 = v_2$, $u_2 = v_3$ and $u_3 = v_4$. Recall that $\gamma_j = \langle w, 1_{T_{u_j}} \rangle$ for $j = 0, 1, 2, 3$, we have $\gamma_1 = 0.33$, $\gamma_2 = 0.12$, $\gamma_3 = 0.45$, and*

$$ \beta(t) = 2 ([\gamma_1 - t]_+ + [\gamma_2 - t]_+ + [\gamma_3 - t]_+). $$
We now compute $\hat{z}(t^*)$. Note that $\bar{z}_0 = 0.05, \bar{z}_1 = 0.15, \bar{z}_2 = 0.1, \bar{z}_3 = 0.15$. The feasibility condition in Proposition 4.3 implies $t \ge 0.315$. On the other hand, the inequality $\beta(t) \le B$ is equivalent to $t \ge 0.3$. By Proposition 4.1, we obtain $t^* = 0.315$. Since $\bar{z}_0 = 0.05 < \frac{\beta(t^*)}{2} = 0.15$, we can choose $\hat{z}(t^*)$ according to (21) by noticing that $J^>(t^*) = \{1,3\}$, $J^\le(t^*) = \{2\}$ and, thus, get

$$ \hat{z}(t^*) = (0.05, -0.015, 0.1, -0.135). $$

By (17), we have

$$ \hat{x}(t^*) = (0.05, -0.005, 0.05, -0.045, -0.005, -0.005, 0.05, -0.045, -0.045). $$

From Proposition 4.1, we may choose $x^* = \hat{x}(t^*)$. Since $w^* = w+x^*$, we obtain

$$ w^* = (0.15, 0.125, 0.11, 0.105, 0.095, 0.095, 0.11, 0.155, 0.055). $$

The maximized lower bound for new stability radius after upgrading is $\underline{R}(w^*) = \frac{0.37}{9}$. Refer to Figure 3 for the weighted tree after upgrading.

<figure><img src="image_4.png" /><figcaption>Figure 3: The tree with optimized weight $w^*$ after upgrading $\underline{R}(\cdot)$.</figcaption></figure>

# 5 Conclusion

In this paper, we examine the stability radius of the median location on a tree network, where vertex weights are variable parameters. We demonstrate that the stability radius has a tight and simple lower bound. Additionally, we explore the problem of enhancing this lower bound by optimizing vertex weights within a given budget, while maintaining the optimality of the original median point. We prove that this problem can be efficiently solved using a combinatorial approach. Our primary technique involves swapping the objective value and budget constraint of the main problem to formulate a parametric problem that can be solved efficiently. In future work, our technique could be extended to analyze the stability of other location problems in various networks, e.g., cactus and block graphs.

# Acknowledgments

This research is funded by Ton Duc Thang University under grant number FOS-TECT.2024.03. The author also thanks Dawson Feng for kindly pointing out
a computational error in Example 4.1, which helped improve the paper. The au-
thor is grateful to the anonymous referees for their valuable comments and sug-
gestions, which have helped improve the quality and clarity of the manuscript.

References

Afrashteh, E, B Alizadeh and F Baroughi (2020). Optimal approaches for up-
grading selective obnoxious p-median location problems on tree networks,
*Annals of Operations Research* 289(2), 153–172.

Alizadeh, B and RE Burkard (2011). Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, *Networks* 58(3), 190–200.

Baldomero-Naranjo, M, J Kalcsics, A Marín and AM Rodríguez-Chía (2022).
Upgrading edges in the maximal covering location problem, *European Journal of Operational Research* 303(1), 14–36.

Blanco, V and A Marín (2019). Upgrading nodes in tree-shaped hub location, *Computers & Operations Research* 102, 75–90.

Burkard, RE, C Pleschiutschnig and J Zhang (2008). The inverse 1-median problem on a cycle, *Discrete Optimization* 5(2), 242–253.

Chakravarti, N and AP Wagelmans (1998). Calculation of stability radii for
combinatorial optimization problems, *Operations Research Letters* 23(1-2),
1–7.

Cooper, L (1978). Bounds on the weber problem solution under conditions of uncertainty. *Journal of Regional Science* 18(1).

Dearing, P, RL Francis and TJ Lowe (1976). Convex location problems on tree networks, *Operations Research* 24(4), 628–642.

Drezner, Z (1985). Sensitivity analysis of the optimal location of a facility, *Naval Research Logistics Quarterly* 32(2), 209–224.

Erkut, E and BC Tansel (1992). On parametric medians of trees, *Transportation science* 26(2), 149–156.

Espejo, I and A Marín (2023). The p-median problem with upgrading of trans-
portation costs and minimum travel time allocation, *Computers & Operations Research* 159, 106354.

Etemad, R and B Alizadeh (2018). Reverse selective obnoxious center location problems on tree graphs, *Mathematical Methods of Operations Research* 87, 431–450.

Gassner, E (2008). Up-and downgrading the 1-median in a network, .
Goldengorin, B, G Jäger and P Molitor (2006). Tolerances applied in combinatorial optimization, *J. Comput. Sci* 2(9), 716–734.

Goldman, AJ (1971). Optimal center location in simple networks, *Transportation science* 5(2), 212–221.

Guan, X and B Zhang (2012). Inverse 1-median problem on trees under weighted hamming distance, *Journal of Global Optimization* 54(1), 75–82.

Kariv, O and S Hakimi (1979). An algorithmic approach to network location problems. ii: The p-medians, *SIAM Journal on Applied Mathematics* 37(3), 539–560.

Karmarkar, N (1984). A new polynomial-time algorithm for linear programming, in *Proceedings of the sixteenth annual ACM symposium on Theory of computing*, pp. 302–311.

Laporte, G, S Nickel and F Saldanha-da Gama (2019). *Introduction to Location Science*, Springer International Publishing: Cham.

Marianov, V and H Eiselt (2024). Fifty years of location theory - a selective review, *European Journal of Operational Research* 318(3), 701–718.

Megiddo, N (1984). Linear programming in linear time when the dimension is fixed, *Journal of the ACM (JACM)* 31(1), 114–127.

Nguyen, KT (2016a). Inverse 1-median problem on block graphs with variable vertex weights, *Journal of optimization theory and applications* 168, 944–957.

Nguyen, KT (2016b). Reverse 1-center problem on weighted trees, *Optimization* 65(1), 253–264.

Nguyen, KT and A Chassein (2015). The inverse convex ordered 1-median problem on trees under chebyshev norm and hamming distance, *European Journal of Operational Research* 247(3), 774–781.

Nguyen, KT, NT Hung, H Nguyen-Thu, TT Le and VH Pham (2019). On some inverse 1-center location problems, *Optimization* 68(5), 999–1015.

Nhan, THN, KT Nguyen and H Nguyen-Thu (2023). The minmax regret reverse 1-median problem on trees with uncertain vertex weights, *Asia-Pacific Journal of Operational Research* 40(03), 2250033.

Pham, VH, KT Nguyen and TT Le (2021). Inverse stable point problem on trees under an extension of chebyshev norm and bottleneck hamming distance, *Optimization Methods and Software* 36(4), 755–772.

Plastria, F (2016). Up-and downgrading the euclidean 1-median problem and knapsack voronoi diagrams, *Annals of Operations Research* 246, 227–251.
Sepasian, AR (2018). Upgrading the 1-center problem with edge length variables on a tree, *Discrete Optimization* 29, 1–17.

Sepasian, AR and F Rahbarnia (2015). Upgrading p-median problem on a path, *Journal of Mathematical Modelling and Algorithms in Operations Research* 14, 145–157.

Tamir, A (1996). An o (pn2) algorithm for the p-median and related problems on tree graphs, *Operations research letters* 19(2), 59–64.

Toan, NT, HM Le and KT Nguyen (2024). The reverse selective balance center location problem on trees, *OPSEARCH* 61(1), 483–497.