کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5128375 1378594 2017 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Greedy algorithms for the single-demand facility location problem
ترجمه فارسی عنوان
الگوریتم های حریصانه برای مسئله ی محل تسهیلات تک-تقاضا
کلمات کلیدی
فهرست مطالب مقاله
چکیده

کلمات کلیدی

1. مقدمه 

2. الگوریتم های حریصانه برای مسئله حداقل-کوله پشتی 

3. یک الگوریتم حریصانه ی 2-تقریب یابی برای مسئله ی محل تسهیلات تک-تقاضا

3.1. علائم و مفاهیم

3.2. الگوریتم حریصانه برای محل تسهیلات تک تقاضا 

4. تعمیم به طرح تقریب یابی زمان چند جمله ای 

 
ترجمه چکیده
در این مقاله، ما الگوریتم های تقریب یابی حریصانه را برای مسئله ی محل تسهیلات تک-تقاضا با الهام گیری از الگوریتم های حریصانه برای مسئله ی حداقل-کوله پشتی که در اصل توسط جنز و لونر (1979) ارائه شده و بعدا توسط کسیریک و همکارانش (1991) تجزیه و تحلیل شد، ارائه می دهیم. ساده ترین الگوریتم، الگوریتم 2-تقریب یابی است که در زمان اجرا می شود، در اصل، ما الگوریتم -تقریب یابی را ارائه می دهیم که در زمان اجرا می شود.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

In this note, we give greedy approximation algorithms for the single-demand facility location problem inspired by the greedy algorithms for the min-knapsack problem originally given by Gens and Levner (1979) and later analyzed by Csirik et al. (1991). The simplest algorithm is a 2-approximation algorithm running in O(nlogn) time; in general, we give a k+1k-approximation algorithm running in O(nklogn) time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 45, Issue 5, September 2017, Pages 452-455
نویسندگان
, ,