مساله مکان یابی مرکز- میانه مسیر استوار با وزن های راسی بازه ای روی شبکه های درختی

در این مقاله، مساله مکانیابی مرکز-میانه مسیر استوار روی شبکه های درختی با وزنهای راسی بازهای یکسان برای هر دو مساله میانه مسیر و مرکز مسیر مورد بررسی قرار میگیرد. تابع هدف استفاده شده در این مقاله، جمع ساده تابع هدف مساله میانه مسیر و مرکز مسیر است. در کارهایی که در ادبیات تحقیقی صورت گرفته است، وزن ریوس برای هر دو مساله مکانیابی میانه مسیر و مرکز مسیر مجزا در نظر گرفته شده است. رویکرد استفاده شده برای محاسبه جواب استوار، رویکرد مینیماکس پشیمانی است. با استفاده از رویکرد مینیماکس پشیمانی، یک الگوریتم ترکیبیاتی با زمان اجرای O(n^5) برای محاسبه جواب استوار مساله مرکز-میانه مسیر استوار روی شبکه های درختی ارایه میشود. در این مقاله، با استفاده از سناریوهای بدترین حالت مسایل مرکز مسیر و میانه مسیر، سناریوهای بدترین حالت مساله مرکز-میانه مسیر استوار پیدا شده و با استفاده از آن، یک جواب استوار برای مساله مورد نظر محاسبه میشود.