Inverse Maximum Dynamic Flow Problem under the Sum-Type Weighted Hamming Distance

Abstract

Inverse maximum flow (IMDF), is among the most important problems in the field of<br />dynamic network flow, which has been considered the Euclidean norms measure in previous<br />researches. However, recent studies have mainly focused on the inverse problems under the<br />Hamming distance measure due to their practical and important applications. In this paper,<br />we studies a general approach for handling the inverse maximum dynamic flow problem<br />under the weighted sum-type Hamming distance. We assume that a dynamic network flow,<br />and a desired feasible dynamic flow on the network is given. We try to adjust the current arc<br />capacity vector to maximize the dynamic flow and minimize the changes. The motivation<br />for this study stems from the Hamming distance that is made practically important in the<br />situation where we only care about the change, disregarding its magnitude. In this paper,<br />first we prove some preliminary results, then we show that this problem (IMDF) can be<br />transformed to a minimum dynamic cut problem. So, we proposed a combinatorial<br />algorithm for solving the IMDF in strongly polynomial time. Ultimately, the proposed<br />algorithm, is illustrated by a numerical example on a dynamic network.