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

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

Keywords:

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