کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429978 | 687761 | 2015 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the minmax regret path median problem on trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
• We study the minmax regret path median problem on a tree.
• The weight of each vertex is uncertain and is characterized by an interval.
• It is required to find a solution minimizing the worst-case loss.
• An improved O(n2)O(n2)-time algorithm is presented.
This paper studies the problem of finding the path median on a tree in which vertex weights are uncertain and the uncertainty is characterized by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. An O(n2)O(n2)-time algorithm is presented, improving the previous upper bound from O(n4)O(n4).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 81, Issue 7, November 2015, Pages 1159–1170
Journal: Journal of Computer and System Sciences - Volume 81, Issue 7, November 2015, Pages 1159–1170
نویسندگان
Jhih-Hong Ye, Biing-Feng Wang,