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

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

کلیدواژه ها:

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