A 3_approximation algorithm for the Facility Location Problem

بسیاری از مسایل پرکاربرد و مهم بهینه سازی در حوزه های مختلف علم وصنعت از مرتبه ی زمانی بالایی برخوردارند و اصولا در گروه مسایل NP-Hard دسته بندی می شوند. از این رو در سال های اخیر گرایش به سمت الگوریتم های تقریبی که در زمان چند جمله ای و با یک ضریب خطا به حل این مسایل می پردازند، افزایش یافته است. در این مقاله یک الگوریتم تقریبی با ضریب تقریب 3 با استفاده از متدهای برنامه ریزی خطی دوگانه و اولیه برای مساله مکان یابی تسهیلات در حالت K لایه ای با توزیع تصادفی ارائه می شود.

کلیدواژه ها:

الگوریتم های تقریبی(approximation algorithms) ، مساله مکان یابی تسهیلات Problem Facility Location ، ضریب تقریبی (approximation ratio) ، بهینه سازی (optimization) ، برنامه ریزی خطی و دوگانه linear programing primal and dual ، تصادفی (Stochastic)