On the complexity of inverse convex ordered 1-median problem on the plane and on tree networks

Abstract

An ordered median function is used in location theory to generalize a class of problems, including median and center problems. In this paper we consider the complexity of inverse ordered 1-median problems on the plane and on trees, where the multipliers are sorted nondecreasingly. Based on the convexity of the objective function, we prove that the problems with variable weights or variable coordinates on the line are NP-hard. Then we can directly get the NP-hardness result for the corresponding problem on the plane. We finally develop a cubic time algorithm that solves the inverse convex ordered 1-median problem on trees with relaxation on modification bounds.

1 Introduction

Inverse optimization problems are playing an important role in operations research with promising applications. In the inverse optimization setting we change parameters in a minimum way of cost so that a prespecified solution becomes optimal with respect to new parameters. For a survey on inverse optimization problem, we refer to Heuberger (2004). Partially, the inverse version of location problems is to modify the parameters of a network or of facilities in the plane to make prespecified facilities optimal in the perturbed problem. In what follows we review the papers concerning inverse location problems.

Let M be the input size of the problem. For the inverse location problem on networks, Burkard et al. (2004) solved the inverse 1-median problem on trees in $O(M\log M)$ time. Then Galavii (2010) improved the complexity of the problem to linear time. Nguyen (2016) considered the inverse 1-median problem on a generalization of tree graphs, the so-called block graphs, and used the convexity of the cost function to develop an algorithm that solves the problem in $O(M\log M)$ time. Also, Burkard et al. (2008) solved the inverse 1-median problem on a cycle in quadratic time based on the concavity of the corresponding linear constraints. Bonab et al. (2011) further considered the inverse p-median problem on networks. They proved that the general problem is NP-hard. However, the inverse 2-median problem on a tree can be solved in polynomial time. Additionally, if the underlying tree is a star, the corresponding problem is solvable in linear time. Then Alizadeh and Bakhteh (2017) applied the firefly algorithm with modification to solve the general inverse p-median problem on the plane. Concerning the inverse center problem, Cai et al. (1999) were the first who showed that although the 1-center problem on networks can be solved in strongly polynomial time, the inverse 1-center problem is NP-hard. Then Alizadeh and Burkard (2011a, b) and Alizadeh et al. (2009) considered the inverse 1-center problem on trees. They developed efficient combinatorial algorithms to solve the problems. Nguyen and Chassein (2015a) also proved that the inverse 1-center problem on cactus graphs, a generalization of trees, is NP-hard. Nguyen and Anh (2015) solved the inverse 1-center problem on trees with variable vertex weights in quadratic time. Furthermore, Nguyen and Sepasian (2016) developed quadratic algorithms to solve the inverse 1-center problem on trees under Chebyshev norm and bottleneck Hamming distance. For the inverse 1-center problem on cycles, Nguyen (2017) proposed an $O(n^2\log n)$ algorithm to solve the problem based on a parameterization approach. Recently, Alizadeh and Etemad (2018) solved some variants of the inverse obnoxious vertex 1-center location problem in strongly polynomial time.

Inverse location problem on the plane is an interesting topic with intensive investigations. The inverse Fermat-Weber problem is solvable in $O(M \log M)$ time by applying a greedy-like method. Moreover, Bonab et al. (2010) investigated the inverse 1-median problem on ${\mathbb {R}}^{d}$ with variable coordinates. They developed an algorithm that solves the corresponding problem with squared Euclidean norm in O(Md) time. In addition, they proved that the problems with rectilinear norm and Chebyshev norm are NP-hard. Hatzl (2012) established an optimality criterion for a point to be a 1-median on ${\mathbb {R}}^{d}$ endowed with Chebyshev norm and he reduced the inverse 1-median problem on this space to a 2-balanced flow problem.

As the decision maker may change the objective function regarding to her/his point of view, a unified approach for location problems is advisable to be studied; one can refer to the book of Nickel and Puerto (2005) for reference. According to the best of our knowledge, Gassner (2012) was the first who studied the inverse ordered 1-median problem. She proved that both the inverse k-centrum problem on weighted trees and the inverse convex ordered 1-median problem on unweighted trees are NP-hard. Moreover, she solved the inverse k-centrum problem on unweighted trees in polynomial time by a dynamic program. Nguyen and Anh (2015) further showed that a generalization of the inverse 1-median and 1-center problems, the so-called inverse k-centrum problem, with variable vertex weights on trees is NP-hard. Also, Nguyen and Chassein (2015b) investigated the inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance. They applied the convexity of the ordered 1-median function on trees and a special property of cost functions to derive polynomial time algorithms that efficiently solve the problems. Although inverse ordered median problems on networks were widely investigated, this problem on the plane has not been studied so far.

This paper addresses the inverse convex ordered 1-median problem on the plane and on tree networks and is organized as follows. Section 2 recalls the preliminary definition and the formal definition of the inverse ordered 1-median problem. We then prove the NP-hardness of some inverse convex ordered 1-median problems on the line and derive the results for the problem on the plane. We investigate in Sect. 3 the inverse convex ordered 1-median problem on trees and develop a cubic time algorithm for the problem with relaxation on the bounds of variables.

2 Inverse convex ordered 1-median problem on the plane

2.1 Problem statement

Let M existing facilities $P_i = (x_i,y_i)$ on the plane be given where each facility $P_i$ is associated with a nonnegative weight $w_i$, for $i=1,\ldots , M$. If all the weights are equal, say 1, we get a set of uniform weighted facilities. Suppose that the plane is endowed with a norm $\Vert .\Vert$, usually involved are the $l_1$-, $l_2$-, or $l_\infty$-norm. Then the distance between two points P and Q is denoted by $d(P,Q) := \Vert P - Q\Vert$. Let $\lambda := (\lambda _1, \lambda _2, \ldots , \lambda _M) \in {\mathbb {R}}^{M}_+$ be a vector of multipliers, the ordered 1-median problem on the plane is to find a new facility, say P, so as to minimize the ordered 1-median function $F_\lambda (P) := \sum _{i=1}^M \lambda _i w_{(i)} d(P,P_{(i)})$, where (.) is a feasible permutation, i.e.,

$$\begin{aligned} w_{(1)} d(P,P_{(1)}) \le w_{(2)} d(P,P_{(2)}) \le \cdots \le w_{(M)} d(P, P_{(M)}). \end{aligned}$$

A point $P_0$ which minimizes $F_\lambda (.)$ is called an ordered 1-median. Furthermore, if we restrict the vector of multipliers $\lambda$ to the condition

$$\begin{aligned} \lambda _1 \le \lambda _2 \le \cdots \le \lambda _M, \end{aligned}$$

(1)

the objective function $F_\lambda (.)$ is convex; see Nickel and Puerto (2005). Especially, if the vector of multipliers is $\lambda := (0,\ldots ,0,1,\ldots ,1)$ with k 1’s, the corresponding problem is called the k-centrum problem. One can observe that the 1-median problem and the 1-center problem are the two special cases of the k-centrum problem, where $k := M$ or $k := 1$. From now on, we always consider the vector of multipliers satisfying (1) or the convex case.

Let M existing points $P_1,\ldots , P_M$ on the plane and a prespecified point $P_0$ be given. Each point $P_i(x_i,y_i)$ is modified to the new coordinate $P_i({\tilde{x}}_i,{\tilde{y}}_i)$, where ${\tilde{x}}_i := x_i + p_{i1} - q_{i1}$ and ${\tilde{y}}_i := y_i + p_{i2} - q_{i2}$ for $i=1,\ldots ,M$. The ordered 1-median function at a point P with respect to the modified facilities is denoted by ${\tilde{F}}_\lambda (.)$. The inverse convex ordered 1-median problem on the plane with variable coordinates is stated as below.

• 1. The point $P_0$ becomes optimal with respect to the new coordinates, i.e., ${\tilde{F}}_\lambda (P_0) \le {\tilde{F}}_\lambda (P)$ for all $P \in {\mathbb {R}}^{2}$.

• 2. The cost function $\ \sum _{i=1}^{M} \sum _{j=1}^{2} \big ( p_{ij} + q_{ij} \big )$ is minimized.

• 3. The variables obey given bounds, i.e., $0 \le p_{ij} \le {\bar{p}}_{ij}$ and $0 \le q_{ij} \le {\bar{q}}_{ij}$ for $i = 1,\ldots ,M$ and $j = 1,2$.

The inverse convex ordered 1-median problem on the plane with variable weights can be stated similarly. In other words, the weight of each point $P_i$ is modified to ${\tilde{w}}_i := w_i + p_i - q_i$, for $i = 1,\ldots ,M$ such that the prespecified point $P_0$ becomes an ordered 1-median with respect to the new facility weights and the modifying cost is minimized. Here, the variations are feasible, i.e., $0 \le p_{i} \le {\bar{p}}_{i}$ and $0 \le q_{i} \le {\bar{q}}_{i}$ for $i = 1,\ldots ,M$.

2.2 Complexity results

We first address the 1-dimensional case, i.e., all the points are located on a line. As a result, the second coordinates of existing facilities can be set to 0 and they are fixed. We denote by L and R the set of points, not coinciding with $P_0$, on the left and the right hand side of $P_0$, respectively. Furthermore, let us remind that the vector of multipliers satisfies (1). We recall the following result by Kalcsics et al. (2002).

Lemma 1

(Optimality criterion in 1-dimensional case) Given the existing facilities $P_1 , P_2, \ldots , P_M$ and a prespecified point $P_0$ on the line. Then $P_0$ is an ordered 1-median if and only if there exist feasible permutations $\sigma _L$ and $\sigma _R$ such that

$$\begin{aligned} \displaystyle \sum _{P_{\sigma _L(i)} \in L} \lambda _i w_{\sigma _L(i)} \le \frac{1}{2} \sum _{i=1}^M \lambda _i w_{\sigma _L(i)}\quad and\quad \displaystyle \sum _{P_{\sigma _R(i)} \in R} \lambda _i w_{\sigma _R(i)} \le \frac{1}{2} \sum _{i=1}^M \lambda _i w_{\sigma _R(i)}. \end{aligned}$$

In ${\mathbb {R}}^{1}$ the distance between two arbitrary points with respect to the norms, $l_1$-, $l_2$-, $l_\infty$-norm, are equal. Thus, we consider only the $l_2$-norm for simplicity. Based on Lemma 1, let us derive the NP-hardness result.

Proposition 1

The inverse k-centrum problem on the line with variable coordinates on ${\mathbb {R}}^1$ is NP-hard.

Proof

Consider an instance $(I^{\le })$ of the $k^{\le }$-partition problem. Given a set $S :=\{a_1 , a_2 , \ldots , a_n\} \subset {\mathbb {N}}$ and $\sum _{i=1}^{n}a_i =2B$. Does there exist $S' \subset S$ with $|S'| \le k$ and $\sum _{a_i \in S'} a_i = B$? The $k^{\le }$-partition problem is NP-hard. Otherwise, we can give an answer to the partition problem in polynomial time by solving at most linearly many $k^{\le }$-partition problems. It contradicts to the NP-hardness of the partition problem; see Garey and Johnson (1979).

We can state the decision version of the inverse $k'$-centrum problem on the line with variable coordinates (InvLC) as: Given an instance of (InvLC), does there exist a feasible solution such that the cost is at most C?

For an instance $(I^{\le })$, we construct an instance (InvLC) in polynomial time as follows.

• Choose $P_0 := 0$ and a point $X := -U$, where U is a sufficiently large number. Moreover, let $P_i := \frac{4B^2 - a_i^{2}}{a_i}$ for $i = 1,\ldots ,n$. Finally, choose $V_1 = V_2 = \cdots = V_k := 8kB^2$.

• Additionally, the corresponding weights are $w_X := B , w_{P_0} := 0 , w_{P_i} := a_i$ for all $i=1, \ldots , n$ and $w_{V_j} := \frac{1}{2k}$ for all $j=1, \ldots , k$.

• Only the coordinate of $P_i$ can be increased by $p_i \in [0,a_i]$ for $i=1,\ldots , n$. Coordinates of other points are fixed.

• Choose $k' := k+1$ and $C := B$.

Observe that, $w_{{\tilde{P}}_i}d({\tilde{P}}_i , P_0) \le w_{V_j}d(V_j , P_0)$ for all $i=1,\ldots , n$ and $j=1,\ldots , k$. Here, ${\tilde{P}}_i$ is the corresponding modified point of $P_i$ for $i=1,\ldots ,n$. The equality holds if ${\tilde{P}}_i := P_i + a_i$. In the current state, the ordered weighted sum of the left side L (containing a point X) is B and the ordered weighted sum of the right side R is $\frac{1}{2}$. Therefore, $P_0$ is not the optimal point of the problem. In what follows, we prove that the answer to $(I^{\le })$ is ’yes’ if and only if the answer to (InvLC) is ’yes’.

Assume that the answer to $(I^{\le })$ is ’yes’, i.e., there exists a subset $S' \subset S$ such that $\sum _{a_i \in S'} a_i = B$ and $|S'|\le k$. We set ${\tilde{P}}_i := P_i + a_i$ for $a_i \in S'$, then $w_{{\tilde{P}}_i}d({\tilde{P}}_i , P_0) = w_{V_j}d(V_j , P_0)$ if $a_i \in S'$. If each $w_{{\tilde{P}}_i}d(P_0,{\tilde{P}}_i)$ for $a_i \in S$ is chosen as one of the $k'$ largest weighted distances to $P_0$, the ordered weighted sum of R is $\sum _{a_i \in S'}a_i + \frac{k-|S'|}{2k} \ge B$. On the other hand, if each $w_{V_j}d(P_0,V_j)$ for $j=1,\ldots , k$ is chosen as one of the $k'$ largest weighted distances to $P_0$, the the ordered weighted sum of R satisfies $\frac{1}{2} \le B$. Hence, there is a feasible solution to (InvLC) such that the objective value is at most B.

Conversely, if there exists a feasible solution to (InvLC) and the objective value is at most B, we prove that the answer to $(I^{\le })$ is ’yes’. Indeed, assume that the specified solution is $(p^{*}_i)_{i=1,\ldots , n}$ and there exists $i_0$ such that $0< p^{*}_{i_0} < a_i$, then $w_{P_{i_0}}d({\tilde{P}}_{i_0} , P_0) < w_{V_j}d(V_j , P_0)$ for $j = 1,\ldots , k$. We have to pay an additional cost but the weighted distance from $P_{i_0}$ to $P_0$ is not one of the $k'$ largest ones. Hence, we can assume that $p^{*}_{i} = 0$ or $p^{*}_{i} = a_i$. Denote by $I := \{ i\in \{1,\ldots , n\}| w_{{\tilde{P}}_i}d({\tilde{P}}_i,P_0) \text{ is } \text{ chosen } \text{ as } \text{ one } \text{ of } \text{ the } k'{} \text{ largest } \text{ weighted } \text{ distances } \}$. Then we have $\sum _{i \in I}a_i + \frac{k - |I|}{2k} \ge B$ due to the optimality criterion. As $a_i , B\in {\mathbb {N}}$ and $\frac{k-|I|}{2k} \in (0,1)$, we get $\sum _{i \in I}a_i \ge B$. Furthermore, as the cost satisfies $\sum _{i \in I}a_i \le B$, we conclude that $\sum _{i \in I}a_i = B$. The result follows. $\square$

We next consider the case of uniform weighted facilities and get a similar result.

Proposition 2

The inverse convex ordered 1-median problem with variable coordinates on ${\mathbb {R}}^1$ is NP-hard even for uniform weights of the existing facilities.

Proof

Consider an instance (I) of the partition problem. Given a set $S := \{a_1 , a_2 , \ldots , a_n\} \subset {\mathbb {N}}$ with $1\le a_1 \le a_2 \le \cdots \le a_n$ and $\sum _{i=1}^{n}a_i =2B$. Does there exist $S' \subset S$ such that $\sum _{a_i \in S'} a_i = B$? Moreover, the decision version of the inverse convex ordered 1-median problem on the line (InvLU) is stated as: Given an instance of (InvLU), does there exist a feasible solution such that the objective value is at most C?

Given an instance (I), we construct an instance (InvLU) in polynomial time as follows.

• Choose $P_0 := 0$ , $P_1 := 1$ , $V_1 := -(a_1 + 1)$, $P_i := -V_{i-1} + 1$ , $V_i := -(P_i + a_i)$ for $i=2, \ldots , n$.

• In addition, the corresponding weights are uniform, i.e., $w_{P_0} = w_{P_i} = w_{V_i} = 1$ for all $i=1, \ldots , n$.

• Only the coordinates of $P_i$ can be increased by $p_i \in [0,a_i]$ for $i = 1,\ldots ,n$. The other coordinates are fixed.

• The vector of multipliers is $\lambda = (m_1 , m_1 + a_1 , m_2 , m_2 + a_2 , \ldots , m_n , m_n + a_n)$, where $m_1> 0$ and $m_{i+1} > m_i + a_i$ for $i=1, \dots , n-1$.

• Choose $C := B$.

One can observes that $d(P_0 , {\tilde{P}}_i) \le d(P_0 , V_i) < d(P_0 , {\tilde{P}}_{i+1}) \le d(P_0 , V_{i+1})$ for $i= 1, \ldots , n-1$. Here, ${\tilde{P}}_i$ is the modified coordinate of $P_i$ for $i = 1,\ldots ,n$. Note that $d(P_0 , {\tilde{P}}_i) = d(P_0 , V_i)$ if we set ${\tilde{P}}_i := P_i + a_i$.

In the current state of the problem, we get $d(P_0 , P_i)< d(P_0 , V_i)< d(P_0 , P_{i+1}) < d(P_0 , V_{i+1})$, for $i= 1, \ldots , n-1$. Then the weighted sum of L is $\sum _{i=1}^{n}a_i + \sum _{i=1}^{n}m_i$ and the weighted sum of R is $\sum _{i=1}^{n}m_i$. Therefore, we aim to increase the coordinates of $P_i$ for $i=1,\ldots , n$ such that $P_0$ becomes an ordered 1-median. In what follows we prove that the answer to (I) is ’yes’ if and only if the answer to (InvLU) is ’yes’.

If the answer to (I) is ’yes’, then there exists $S' \subset S$ such that $\sum _{a_i \in S'} a_i = B$. We set ${\tilde{P}}_i := P_i + a_i$ for $a_i \in S'$. Then $d(P_0 , {\tilde{P}}_i) = d(P_0 , V_i)$ for $a_i \in S'$. The objective value is $\sum _{a_i \in S'} a_i = B$. Moreover, we consider the sorting of distances as $d(P_0,{\tilde{P}}_i) < d(P_0,V_i)$ for $a_i \not \in S'$ and $d(P_0,V_i) \le d(P_0,{\tilde{P}}_i)$ for $a_i \in S'$. Then the ordered weighted sum of the right part R is $\sum _{a_i \in S'}a_i + \sum _{i=1}^{n}m_i = B + \sum _{i=1}^{n}m_i$, and it is equal to the ordered weighted sum of the left part L. Therefore, $P_0$ becomes an ordered 1-median and the cost is B.

Conversely, assume that there exists a feasible solution such that the objective value is at most B. Assume that $(p^{*}_i)_{i = 1,\ldots ,n}$ is the specified feasible solution. By the similar argument as in Proposition 1, we can assume that $p^{*}_{i} = 0$ or $p^{*}_{i} = a_i$ for all $i=1 ,\ldots , n$. Denote by $I := \{i \in \{1,\ldots , n\}| p^{*}_{i} = a_i \}$. The cost is $\sum _{i\in I} a_i \le B$. Because of the optimality criterion, the maximum ordered weighted sum of R satisfies $\sum _{i \in I}a_i + \sum _{i=1}^{n}m_i \ge \sum _{i \not \in I}a_i + \sum _{i=1}^{n}m_i$ or $\sum _{i \in I}a_i \ge B$. Thus, we have $\sum _{i \in I}a_i = B$. The answer to (I) is ’yes’. $\square$

For another version of the inverse location problem concerning the variation of facility weights, we also get the complexity result as follows.

Proposition 3

The inverse k-centrum problem with variable weights on ${\mathbb {R}}^1$ is NP-hard.

Proof

The decision version of the inverse $k'$-centrum problem with variable weights (InvLW) is: Given an instance of (InvLW), does there exist a feasible solution such that the objective value is at most C? Given an instance $(I^{\le })$ of $k^{\le }$-partition problem (as introduced in Proposition 1), we construct the instance (InvLW) in polynomial time as follows.

• Let $P_0 := 0 , X := - B, P_i := \frac{B}{2ka_i}$ for $i=1,\ldots , n$ and $V_j := B$ for $j=1,\ldots , k$.

• The corresponding weights are $w_{P_i} := 0$ for $i = 0, 1,\ldots , n$, $w_X := B$ and $w_{V_j} := \frac{1}{2k}$ for $j=1, \ldots , k$.

• The weights of $P_i$ for $i = 1,\ldots ,n$ can be increased by $p_i \in [0,a_i]$. The weights of other points are fixed.

• Choose $k' := k+1$ and $C := B$.

Similar to the technique in Propositions 1 and 2, we can prove that the answer to $(I^{\le })$ is ’yes’ if and only if the answer to (InvLW) is ’yes’. Then the lemma follows. $\square$

From the complexity result of the inverse ordered 1-median problem on the line, we can directly derive the complexity result for this problem on the plane.

Theorem 1

The inverse convex ordered 1-median problem on the plane with variable coordinates or variable point weights is NP-hard.

3 Inverse convex ordered 1-median problem on trees

3.1 Problem statement

Let us revisit the ordered 1-median problem on trees. Let a connected graph $G = (V,E)$ with vertex set $V := \{v_1,v_2,\ldots ,v_M\}$ be given where each vertex $v_i \in V$ is associated with a nonnegative weight $w_i$ and each edge $e\in E$ has a nonnegative length $\ell _e$. If all vertex weights in G are equal, say 1, we obtain an unweighted network. By definition, a point in G is either a vertex or lies on an edge of the network. The set of all points in G is denoted by A(G). The distance d(a, b) between two points a and b is the length of the shortest path connecting them. Given a vector of multipliers $\lambda := (\lambda _1,\lambda _2,\ldots ,\lambda _M)$, the ordered 1-median function at $\rho \in A(G)$ is defined as $F_{\lambda } (\rho ) := \sum _{i=1}^{M} \lambda _i w_{(i)} d(\rho ,v_{(i)})$. Here, the operator (.) is a permutation of $\{1,2,\ldots ,M\}$ so that the weighted distances to the point $\rho$ are sorted nondecreasingly, i.e.,

$$\begin{aligned} w_{(1)}d(\rho ,v_{(1)}) \le w_{(2)}d(\rho ,v_{(2)}) \le \cdots \le w_{(M)}d(\rho ,v_{(M)}). \end{aligned}$$

The permutation (.) is called a feasible permutation. We further denote the set of all feasible permutations by $\Pi$. Additionally, a point $\rho ^{*}$ is, by definition, an ordered 1-median of G if $F_{\lambda }(\rho ^{*}) \le F_\lambda (\rho )$ for all $\rho$ in A(G). If the underlying graph is a tree and the multipliers satisfies (1), then the ordered 1-median function is convex along each simple path of the tree; see Nickel and Puerto (2005).

For a tree network $T = (V,E)$ and a prespecified vertex $v^{*}$, let ${\mathcal {T}}(v^{*})$ be the set of all subtrees induced by deleting $v^{*}$ and its incident edges. We recall the optimality criterion for a vertex to be a 1-median on the tree T as follows.

Theorem 2

(Optimality criterion; see Gassner (2012) and Kalcsics et al. (2002)) Given a tree $T = (V,E)$ and a vector of multipliers $\lambda \in \mathbb R^{M}_+$ with $\lambda _1 \le \lambda _2 \le \cdots \le \lambda _M$. Then the prespecified vertex $v^{*}$ is an ordered 1-median of T if and only if for each subtree $T^{sub} \in {\mathcal {T}}(v^{*})$ there exists a feasible permutation $\sigma ^{sub}$ such that

$$\begin{aligned} \displaystyle \sum _{v_{\sigma ^{sub}(i)} \in T^{sub}}\lambda _iw_{\sigma ^{sub} (i)} \le \sum _{v_{\sigma ^{sub}(i)} \not \in T^{sub}}\lambda _i w_{\sigma ^{sub} (i)}. \end{aligned}$$

Given a tree $T=(V,E)$, a prespecified vertex $v^{*}$, and a vector of multipliers $\lambda \in {\mathbb {R}}^{n}_+$. The length of each edge e can be increased or reduced by $p_e$ or $q_e$. This means the modified length of an edge e is ${\tilde{\ell }}_e := \ell _e + p_e - q_e$ (assumed to be nonnegative, hence one can suppose $q_e \le \ell _e$). The cost to increase or decrease one unit length of e is $c^{+}_e$ or $c^{-}_e$, respectively. The inverse ordered 1-median problem on T is formally stated as the following.

• 1. The cost function $\sum _{e\in E} (c^{+}_ep_e + c^{-}_eq_e)$ is minimized.

• 2. The prespecified vertex $v^{*}$ becomes an ordered 1-median of the perturbed tree.

• 3. The modifications are in certain bounds, i.e., $0 \le p_e \le {\bar{p}}_e$ and $0 \le q_e \le {\bar{q}}_e$.

If $c^{+}_e = c^{-}_e = 1$ for all $e \in E$, the corresponding problem is the uniform-cost one.

3.2 Uniform-cost convex problem with relaxation

From here on, we always assume that $\lambda _1 \le \lambda _2 \le \cdots \le \lambda _M$, i.e., the ordered 1-median problem is convex. The inverse convex ordered 1-median problem on trees was first investigated by Gassner (2012). She proved that the inverse convex ordered 1-median problem on uniform weighted trees is NP-hard. In this section we further investigate the uniform-cost inverse convex ordered 1-median problem on an unweighted tree $T=(V,E)$ with relaxation of certain bounds (InvT). It means we relax Condition 3. in the formulation of the problem stated previously.

For each $T^{sub} \in {\mathcal {T}}(v^{*})$ we denote by $\Lambda _{T^{sub}} := \min _{\sigma \in \Pi } \sum _{v_{\sigma (i)}\in T^{sub}}\lambda _i$ and $\Lambda '_{T^{sub}} := \sum _{i=1}^{n}\lambda _i - \Lambda _{T^{sub}}$. Note that one can rewrite $\Lambda '_{T^{sub}} := \max _{\sigma \in \Pi } \sum _{v_{\sigma (i)}\not \in T^{sub}}\lambda _i$. To find $\Lambda _{T^{sub}}$, we apply the priority in the sorting of distances, i.e., if two vertices $v \in T^{sub}$ and $v' \in T\backslash T^{sub}$ have the same distance to $v^{*}$, then v gets a smaller index as $v'$ in the ordering. For this priority, we get a feasible permutation $\sigma ^{sub}$ such that $\Lambda _{T^{sub}} := \sum _{v_{\sigma ^{sub} (i)}\in T^{sub}}\lambda _i$. By Theorem 2, we directly derive the following simplification.

Corollary 1

(Ordered 1-median criterion) The vertex $v^{*}$ is an ordered 1-median of T if and only if $\Lambda _{T^{sub}} \le \Lambda '_{T^{sub}}$ for all $T^{sub} \in {\mathcal {T}}(v^{*})$,

Assume that $v^{*}$ is not an ordered 1-median of T, then there exists exactly one subtree $T' \in {\mathcal {T}}(v^{*})$ such that $\Lambda _{T'} > \Lambda '_{T'}$. Denote by ${\mathcal {G}} := \Lambda _{T'} - \Lambda '_{T'}$ the positive the gap. Let $T'^{*}$ be the subtree induced by $T'\cup \{v^{*}\}$, we have an obvious, but useful, property as follows.

Proposition 4

In the optimal solution of (InvT), it is sufficient to decrease the length of edges in $T'^{*}$ and increase the length of edges in $T\backslash T'^{*}$.

By Proposition 4, we can simplify the cost function as $\sum _{e\in T'^{*}}q_e + \sum _{e\in T\backslash T'^{*}}p_e$. We further show that there exists an optimal solution where we only reduce the edge lengths.

Observe that the gap ${\mathcal {G}}$ can be reduced if the orders of vertices in $T'$ and $T\backslash T'$ changes. It means that, there exist $v' \in T'$ and $v'' \in T\backslash T'$ satisfying $d(v^{*},v') > d(v^{*},v'')$, but ${\tilde{d}}(v^{*},v') = {\tilde{d}}(v^{*},v'')$ after the modification. Here, the distances ${\tilde{d}}$ corresponds to the new edge lengths ${\tilde{\ell }}$. Moreover, if an edge $(v^{*},v)$ for $v \in T'$ is modified to 0, the vertex v coincides with $v^{*}$. We say that a topology change occurs as the set ${\mathcal {T}}(v^{*})$ changes; see Alizadeh and Burkard (2011b). In other words, some vertices in $T'$ are removed from this subtree. The gap ${\mathcal {G}}$ has to be further reevaluated with respect to the new structure of $\mathcal T(v^{*})$. We denote the difference of distances from $v' \in T'$ and $v\in T\backslash T'$ to $v^{*}$ by $r(v',v) := d(v^{*},v') - d(v^{*},v)$ and set

$$\begin{aligned} {\mathcal {R}} := \{(v',v): v'\in T', v\in T\backslash T' \text{ and } r(v',v) > 0\}. \end{aligned}$$

Then the orders of vertices in $T'$ and $T\backslash T'$ change if there exists $(v',v) \in {\mathcal {R}}$ such that ${\tilde{r}}(v',v) := {\tilde{d}}(v^{*},v') - {\tilde{d}}(v^{*},v) = 0$ with respect to the new edge lengths ${\tilde{\ell }}$.

For a sufficiently small value x, a modification of edge lengths is called the most benefit if the number of pairs $(v',v) \in {\mathcal {R}}$, such that $r(v',v)$ is reduced, is maximum among all modifications with the cost x. In the following we investigate which is the most benifit modification for a sufficiently small cost x.

Proposition 5

For a sufficiently small cost x, we get the most benifit modification by reducing the length of $(v^{*},v_0)$, where $v_0 \in T'$ is an adjacent vertex of $v^{*}$.

Proof

We denote the subtrees in ${\mathcal {T}}(v^{*})$ different from $T'$ by $T'_1,T'_2,\ldots ,T'_n$. As an arbitrary modification can be switched to the edges near the root node $v^{*}$ first, we concentrate on the augmentation of $(v^{*},v_i)$, where $v_i \in T_i$ is an adjacent vertex of $v^{*}$ for $i=1,\ldots ,n$, or the reduction of $(v^{*},v_0)$. Assume that we increase the length of $(v^{*},v_i)$ for $i \in \{1,\ldots ,n\}$ by x. Then the relation of a pair $(v',v) \in {\mathcal {R}}$ is

$$\begin{aligned} r^{1}(v',v) := {\left\{ \begin{array}{ll} d(v^{*},v') - d(v^{*},v) - x, &{}\quad \hbox {if } v \in T'_i \\ d(v^{*},v') - d(v^{*},v), &{}\quad \hbox {otherwise}. \end{array}\right. } \end{aligned}$$

On the other hand, if we decrease the length of $(v^{*},v_0)$ by an amount x, the relations of a pair $(v',v) \in {\mathcal {R}}$ is updated as $r^{2}(v',v) := d(v^{*},v') - d(v^{*},v) - x$. For a pair $(v',v) \in {\mathcal {R}}$ with $v'\in T'$ and $v\in T\backslash T'$, we get $r^{2}(v',v) \le r^1(v',v)$. Thus, we get the most benefit modification if the edge $(v^{*},v_0)$ is reduced by x. $\square$

By Proposition 5, we can assign $p_e := 0$ for $e \not \in T'^{*}$ and simplify the cost function as $\sum _{e\in T'^{*}}q_e$.

Let us consider the case that the gap remains positive until the topology change occurs. We first reduce the length of edge $(v^{*},v_0)$ to 0, where $v_0 \in T'$ is an adjacent vertex of $v^{*}$. Then some vertices in $T'$ move to the complementary part $T \backslash T'$. The set ${\mathcal {T}}(v^{*})$ is also updated, i.e., it is the set of all subtrees induced by deleting $v^{*}$ and $v_0$ and their incident edges. Let ${\mathcal {T}}'(v^{*})$ be the set of subtrees in ${\mathcal {T}}(v^{*})$ which are also the subtrees of $T'$ . We first identify the subtree $T'_{\max }$ such that $\Lambda _{T'_{\max }} := \max \{\Lambda _{T''} : T'' \in \mathcal T'(v^{*}) \}$. If $\Lambda _{T'_{\max }} \le \Lambda _{T'_{\max }}'$, we observe that $v^{*}$ becomes an ordered 1-median of T. Otherwise, we continue the reduction of edge length $(v^{*},v_{(1)})$ for a vertex $v_{(1)} \in T'_{\max }$ adjacent to $v^{*}$ and represent the gap as ${\mathcal {G}} := \Lambda _{T'_{\max }} - \Lambda _{T'_{\max }}'$.

Based on the property of the problem, we now develop an algorithm to solve this problem; see Algorithm 1. The main idea of the algorithm is first to find the subtree $T'$ in $\mathcal T(v^{*})$ that violates the optimality criterion, otherwise the problem is trivial. Then we reduce the incident edge (in $T'$) of $v^{*}$ to improve the gap. We stop at the time the gap becomes nonpositive.

In Line 5 of Algorithm 1, we can find the amount x by the following procedure. We first sort the vertices with priority to $T'$. For the vertex v in $T'$ with greatest ordering comparing to other vertices in $T'$, we consider a vertex $v'$ in $T\backslash T'$ with maximum ordering that is smaller than the ordering of v. Then we find $x_v$ such that $d(v^{*},v) - x_v = d(v^{*},v')$ or $x_v := d(v^{*},v) - d(v^{*},v')$. In the next step we start with a vertex $v''$ in $T'$ with maximum ordering that is smaller than the ordering of $v'$ and stop the loop until the vertex with minimum ordering in $T'$ is considered. The minimum among the identified amounts $x_v$ and $\ell _{(v^*,v_0)}$ is x, where $(v^*,v_0)$ is the reducing edge. This procedure is indeed completed in linear time.

We now analyze the complexity of Algorithm 1. We can check the optimality criterion and find $T'$ in $O(M\log M)$ time. In each iteration the minimum modification, for which the gap ${\mathcal {G}}$ can be reduced or a topology change occurs, can be found in linear time. We can update ${\mathcal {G}}$ in O(M) time based on the latest vertex orders. As there are at most $O(M^{2})$ changes of vertex orders, the algorithm runs in $O(M^{3})$ time. Hence, we finally get the main theorem of this section.

Theorem 3

The uniform-cost inverse convex ordered 1-median problem on unweighted trees with relaxation on certain bounds can be solved in $O(M^{3})$ time, where M is the number of vertices of trees.

We illustrate Algorithm 1 by the following example.

Example 1

Given an instance of a tree $T = (V,E)$ with a prespecified vertex $v_1$ as depicted in Fig. 1. The vector of multipliers is $\lambda = (0,0,1,2,3,5)$. Applying the priority in the sorting of distances, we get a feasible permutation $\sigma$ with priority to $T'$ induced by $\{v_3,v_4,v_5,v_6\}$ as $\sigma (1) = 1$, $\sigma (2) = 3$, $\sigma (3) = 2$, $\sigma (4) = 5$, $\sigma (5) = 4$, $\sigma (6) = 6$. The subtree $T'$ therefore violates the optimality criterion as ${\mathcal {G}} := \Lambda _{T'} - \Lambda _{T'}' = 9 > 0$. Thus, we apply Algorithm 1 to solve the problem in the following iterations.

• Iter. 1. We reduce $(v_1,v_3)$ by 1 and obtain a topology change ($v_3 \equiv v_1$). The subtree $T'_{\max } := \{v_5,v_6\} \in {\mathcal {T}}(v_1)$ violates the optimality criterion as ${\mathcal {G}} := \Lambda _{T'_{\max }} - \Lambda _{T'_{\max }}' = 1 > 0$.

• Iter. 2. We reduce the length of $(v_1,v_5)$ by 1 such that the orders of $v_4$ and $v_6$ change. The gap is updated to ${\mathcal {G}} := -3$. Hence, the optimal cost is 2 and the corresponding modified tree is depicted as in Fig. 2.

Fig. 1

An instance of the problem

Fig. 2

The final perturbed tree

4 Conclusions

We addressed the complexity of inverse convex ordered 1-median problems on the plane and on networks. It is shown in one hand that the inverse convex ordered 1-median problem on the plane with variable coordinates or weights is NP-hard. On the other hand, the problem on unweighted trees can be solved in cubic time if we relax the bounds on variables. For future research, we suggest to investigate heuristic approaches or approximation schemes of the NP-hard inverse ordered 1-median on the plane or on networks.