کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332692 | 687746 | 2016 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient algorithms for the round-trip 1-center and 1-median problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
This paper presents improved algorithms for the round-trip single-facility location problem on a general graph, in which a set A of collection depots is given and the service distance of a customer is defined to be the distance from the server, to the customer, then to a depot, and back to the server. Each customer i is associated with a subset AiâA of depots that i can potentially select from and use. When Ai=A for each customer i, the problem is unrestricted; otherwise it is restricted. For the restricted round-trip 1-center problem, we give an O(mnlgâ¡n)-time algorithm. For the restricted 1-median problem, we give an O(mnlgâ¡(|A|/m)+n2lgâ¡n)-time algorithm. For the unrestricted 1-median problem, we give an O(mn+n2lgâ¡lgâ¡n)-time algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 82, Issue 5, August 2016, Pages 782-792
Journal: Journal of Computer and System Sciences - Volume 82, Issue 5, August 2016, Pages 782-792
نویسندگان
Biing-Feng Wang, Jhih-Hong Ye, Pei-Jung Chen,