کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876156 | 690239 | 2014 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Robust fault tolerant uncapacitated facility location
ترجمه فارسی عنوان
محل کارخانه ضمانت ضعف مقاوم در برابر خطا
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
سلام، الگوریتم های تقریبی، تحمل خطا،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In the uncapacitated facility location problem, given a graph, a set of demands and opening costs, it is required to find a set of facilities R, so as to minimize the sum of the cost of opening the facilities in R and the cost of assigning all node demands to open facilities. This paper concerns the robust fault-tolerant version of the uncapacitated facility location problem (RFTFL). In this problem, one or more facilities might fail, and each demand should be supplied by the closest open facility that did not fail. It is required to find a set of facilities R, so as to minimize the sum of the cost of opening the facilities in R and the cost of assigning all node demands to open facilities that did not fail, after the failure of up to α facilities. We present a polynomial time algorithm that yields a 6.464-approximation for this problem with at most one failure and a 1.488+7.464α-approximation for the problem with at most α failures for a fixed α>1. We also show that the RFTFL problem is NP-hard even on trees, and even in the case of a single failure.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 543, 10 July 2014, Pages 9-23
Journal: Theoretical Computer Science - Volume 543, 10 July 2014, Pages 9-23
نویسندگان
Shiri Chechik, David Peleg,