Approximation algorithm for maximum flow network interdiction problem

  • سال انتشار: 1399
  • محل انتشار: مجله ایرانی آنالیز عددی و بهینه سازی، دوره: 10، شماره: 1
  • کد COI اختصاصی: JR_IJNAO-10-1_001
  • زبان مقاله: انگلیسی
  • تعداد مشاهده: 301
دانلود فایل این مقاله

نویسندگان

Maria Afsharirad

Department of Mathematics, University of Science and Technology of Mazandaran, P.O.Box: ۴۸۵۱۸-۷۸۱۹۵, Behshahr, Iran.

چکیده

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.

کلیدواژه ها

Interdiction ‎, ‎ Approximation algorithm ‎, ‎ Network flow ‎, ‎ Minimum capacity cut

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.