الگوریتم های جواب برای مسئله مکان یابی مرکز- میانه استوار روی گراف ها

در این مقاله، مسئله ی مکان یابی مرکز - میانه استوار مطلق/ راسی با وزن های راسی غیرقطعی به ترتیب، روی درخت ها و روی گراف های کلی مورد مطالعه قرار می گیرد. معیار مورد استفاده برای حل مسئله در این مقاله معیار مینی- ماکس پشیمانی است. این مسئله با دو نوع تابع هدف مورد بررسی قرار گرفته و الگوریتم های چندجمله ای برای هر دو نوع ارائه می شود. نشان داده می شود که مسئله ی مرکز - میانه استوار مطلق روی درخت ها و مسئله ی مرکز - میانه راسی روی گراف های کلی به ترتیب در زمان های O(n3 log n) و O(n3) حل می شوند.

Keywords:

مسئله ی مکان یابی مرکز , میانه , مینی , ماکس پشیمانی , بهینه سازی استوار