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

Document Type : research paper


1 Phd Student of Mathematics, Karaj Branch, Isalmic Azad University, Karaj, Iran

2 Department of Mathematics, Karaj Branch, Isalmic Azad University, Karaj, Iran


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


Article Title [فارسی]

حل مسئله معکوس ماکزیمم جریان در شبکه پویا تحت فاصله همینگ تجمعی وزندار

Authors [فارسی]

  • هاجر بنی خادمی 1
  • حسن صالحی فتح آبادی 2
1 دانشجوی دکتری، گروه ریاضی، دانشگاه آزاد اسلامی واحد کرج، کرج، ایران
2 عضو هیأت علمی، گروه ریاضی، دانشگاه آزاد اسلامی واحد کرج، کرج، ایران
Abstract [فارسی]

معکوس ماکزیمم جریان پویا یکی از مهمترین مسائل شبکه های جریان میباشد که در تحقیقات پیشین، تحت معیار فاصله
اقلیدسی مورد بررسی قرار گرفته است. اما اخیراً مطالعات گستردهای در زمینه مسائل معکوس در شبکه های ایستا تحت معیار
همینگ، که ناشی از کاربردهای عملی آن است، انجام گرفته است. لذا در این مقاله معکوس ماکزیمم جریان را در شبکه پویا
تحت معیار همینگ مورد بررسی قرار میدهیم. برای جریان داده شده در شبکه پویا، میخواهیم با کمترین تغییرات ممکن در
بردار ظرفیت کمانها، جریان داده شده، ماکزیمم جریان در شبکه باشد. بکارگیری فاصله همینگ بدلیل کاربردهای عملی آن
در مواقعی که در آن تنها تعداد کمانهایی که ظرفیتشان تغییر میکند بدون در نظر گرفتن بزرگی تغییرات، برایمان اهمیت
دارد. لذا در این مقاله بعد از اثبات نتایج اولیه، یک مسئله کمترین برش پویا برای حل معکوس ماکزیمم جریان ارائه شده
است. همچنین الگوریتم بر مبنای بهینه سازی ترکیبیاتی برای حل مسئله معکوس در زمان چندجملهای ارائه شده است و در
نهایت الگوریتم پیشنهادی روی یک شبکه نمونه پیاده سازی شده است.

Keywords [فارسی]

  • بهینه سازی معکوس
  • شبکه جریان پویا
  • فاصله همینگ
  • نرم اقلیدسی