Network interdiction problems by deleting critical edges have wide applicatio ns. However, in some practical applications, the goal of deleting edges is difficult to achieve. We consider the maximum ...shortest path interdiction problem by upgrading edges on trees (MSPIT) under unit/weighted
l
1
norm. We aim to maximize the the length of the shortest path from the root to all the leaves by increasing the weights of some edges such that the upgrade cost under unit/weighted
l
1
norm is upper-bounded by a given value. We construct their mathematical models and prove some properties. We propose a revised algorithm for the problem (MSPIT) under unit
l
1
norm with time complexity
O
(
n
), where
n
is the number of vertices in the tree. We put forward a primal dual algorithm in
O
(
n
2
)
time to solve the problem (MSPIT) under weighted
l
1
norm, in which a minimum cost cut is found in each iteration. We also solve the problem to minimize the cost to upgrade edges such that the length of the shortest path is lower bounded by a value and present an
O
(
n
2
)
algorithm. Finally, we perform some numerical experiments to compare the results obtained by these algorithms.
We consider the capacitated inverse optimal value problem on minimum spanning tree under Hamming distance. Given a connected undirected network
G
=
(
V
,
E
)
and a spanning tree
T
0
, we aim to ...modify the weights of the edges such that
T
0
is not only the minimum spanning tree under the new weights but also the weight of
T
0
is equal to a given value
K
. The objective is to minimize the modification cost under bottleneck Hamming distance. We add a lower bound
l
and an upper bound
u
on the modification of weights and consider three cases (uncapacitated, lower bounded, capacitated) of the problem based on the bound vectors. Suppose
l
=
-
∞
,
u
=
+
∞
in the uncapacitated problem,
l
>
-
∞
,
u
=
+
∞
in the lower bounded problem and
l
>
-
∞
,
u
<
+
∞
in the capacitated problem. We present three mathematical models of these problems. After analyzing the properties, we develop three strongly polynomial time algorithms based on binary search to solve the problems. The time complexities for solving the uncapacitated, the lower bounded and capacitated problems are all
O
(
|
V
|
|
E
|
log
|
E
|
)
time. Finally, we do some numerical experiments to show the effectiveness of the algorithms.
Network interdiction problems by upgading critical edges/nodes have important applications to reduce the infectivity of the COVID-19. A network of confirmed cases can be described as a rooted tree ...that has a weight of infectious intensity for each edge. Upgrading edges (nodes) can reduce the infectious intensity with contacts by taking prevention measures such as disinfection (treating the confirmed cases, isolating their close contacts or vaccinating the uninfected people). We take the sum of root-leaf distance on a rooted tree as the whole infectious intensity of the tree. Hence, we consider the sum of root-leaf distance interdiction problem by upgrading edges/nodes on trees (SDIPT-UE/N). The problem (SDIPT-UE) aims to minimize the sum of root-leaf distance by reducing the weights of some critical edges such that the upgrade cost under some measurement is upper-bounded by a given value. Different from the problem (SDIPT-UE), the problem (SDIPT-UN) aims to upgrade a set of critical nodes to reduce the weights of the edges adjacent to the nodes. The relevant minimum cost problem (MCSDIPT-UE/N) aims to minimize the upgrade cost on the premise that the sum of root-leaf distance is upper-bounded by a given value. We develop different norms to measure the upgrade cost. Under weighted Hamming distance, we show the problems (SDIPT-UE/N) and (MCSDIPT-UE/N) are NP-hard by showing the equivalence of the two problems and the 0–1 knapsack problem. Under weighted
l
1
norm, we solve the problems (SDIPT-UE) and (MCSDIPT-UE) in
O
(
n
) time by transforimg them into continuous knapsack problems. We propose two linear time greedy algorithms to solve the problem (SDIPT-UE) under unit Hamming distance and the problem (SDIPT-UN) with unit cost, respectively. Furthermore, for the the minimum cost problem (MCSDIPT-UE) under unit Hamming distance and the problem (MCSDIPT-UN) with unit cost, we provide two
O
(
n
log
n
)
time algorithms by the binary search methods. Finally, we perform some numerical experiments to compare the results obtained by these algorithms.
We consider the lower bounded inverse optimal value problem on minimum spanning tree under unit
l
∞
norm. Given an edge weighted connected undirected network
G
=
(
V
,
E
,
w
)
, a spanning tree
T
0
, ...a lower bound vector
l
and a value
K
, we aim to find a new weight vector
w
¯
respecting the lower bound such that
T
0
is a minimum spanning tree under the vector
w
¯
with weight
K
, and the objective is to minimize the modification cost under unit
l
∞
norm. We present a mathematical model of the problem. After analyzing optimality conditions of the problem, we develop a strongly polynomial time algorithm with running time
O
(|
V
||
E
|). Finally, we give an example to demonstrate the algorithm and present the numerical experiments.
The inverse 1-median problem consists in modifying the weights of the customers at minimum cost such that a prespecified supplier becomes the 1-median of modified location problem. A linear time ...algorithm is first proposed for the inverse problem under weighted
l
∞
norm. Then two polynomial time algorithms with time complexities
O
(
n
log
n
) and
O
(
n
) are given for the problem under weighted bottleneck-Hamming distance, where
n
is the number of vertices. Finally, the problem under weighted sum-Hamming distance is shown to be equivalent to a 0-1 knapsack problem, and hence is
-hard.
In this paper, we consider a class of inverse constrained bottleneck problems (ICBP). Given two weight vectors
w
1
and
w
2
, the constrained bottleneck problem is to find a solution that minimizes
w
...1
-bottleneck weight subject to a bound constraint on
w
2
-sum weight. In its inverse problem (ICBP), however, a candidate solution is given, and we wish to modify the two weight vectors under bound restrictions so that the given solution becomes an optimal one to the constrained bottleneck problem and the deviation of the weights under weighted
l
∞
norm is minimum. When the modifications of the two weight vectors are proportional, we present a general method to solve the problem (ICBP) and give several examples to implement the method including the inverse constrained bottleneck spanning tree problem and the inverse constrained bottleneck assignment problem.
Network interdiction problems by deleting critical edges have wide applicatio ns. However, in some practical applications, the goal of deleting edges is difficult to achieve. We consider the maximum ...shortest path interdiction problem by upgrading edges on trees (MSPIT) under unit/weighted Formula omitted norm. We aim to maximize the the length of the shortest path from the root to all the leaves by increasing the weights of some edges such that the upgrade cost under unit/weighted Formula omitted norm is upper-bounded by a given value. We construct their mathematical models and prove some properties. We propose a revised algorithm for the problem (MSPIT) under unit Formula omitted norm with time complexity O(n), where n is the number of vertices in the tree. We put forward a primal dual algorithm in Formula omitted time to solve the problem (MSPIT) under weighted Formula omitted norm, in which a minimum cost cut is found in each iteration. We also solve the problem to minimize the cost to upgrade edges such that the length of the shortest path is lower bounded by a value and present an Formula omitted algorithm. Finally, we perform some numerical experiments to compare the results obtained by these algorithms.
In a shortest path improvement problem under unit Hamming distance (denoted by SPIUH), an edge weighted graph with a set of source-terminal pairs is given; we need to modify the lengths of edges by a ...minimum cost under unit Hamming distance such that the modified distances of the shortest paths are upper bounded by given values. The SPIUH problem on arborescent network is formulated as a 0-1 integer programming model. Some strongly polynomial time algorithms are designed for the problems on some special arborescent networks. Firstly, two greedy algorithms are proposed for problems on chain networks and special star-tree networks, respectively. Secondly, a strongly polynomial time algorithm is presented for the problem with a single source and constrained paths. Finally, a heuristic algorithm and its computational experiments are given for the SPIUH problem on general graphs.
PDF
