approximation algorithm for maximum flow network interdiction problem

We consider the maximum flow network interdiction problem. we provide a new interpretation of the problem and define a concept called ”optimalcut”. we propose a heuristic algorithm to obtain an approximated cut, and we also obtain its error bound. finally, we show that our heuristic is an α-approximation algorithm for a class of networks. by implementing it on three network types, we show the advantage of it over solving the model by cplex.

الگوریتم تقریبی برای مساله ممانعت از بیشترین جریان شبکه

در این مقاله به بررسی مساله ممانعت از بیشترین جریان شبکه می‌پردازیم. نخست تعبیر جدیدی از مساله را ارائه داده و سپس مفهوم برش بهینه را تعریف می‌کنیم. یک الگوریتم ابتکاری برای یافتن تقریبی از برش بهینه پیشنهاد می‌کنیم. در نهایت نشان خواهیم داد که روش ابتکاری پیشنهادی برای نوع خاصی از شبکه‌ها، تبدیل به یک الگوریتم آلفاتقریب خواهد شد. با اجرای الگوریتم بر روی سه نوع شبکه مختلف، برتری این روش را نسبت به حل مستقیم مدل بااستفاده از CPLEX نشان خواهیم داد.