کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949962 1440208 2016 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Combinatorial approximation algorithms for buy-at-bulk connected facility location problems
ترجمه فارسی عنوان
الگوریتم تقسیم ترکیبی برای مشکلات خرید محل اتصال در محل خرید
کلمات کلیدی
مکان یابی متصل طراحی شبکه خرید و فروش، الگوریتم تقریبی، ارتباطات مخابراتی،
ترجمه چکیده
در این مقاله، دو نسخه اساسی این مشکلات را معرفی و تحلیل می کنیم. در نسخه خرید در فله مشکل، هر نوع کابل دسترسی دارای هزینه نصب ثابت و ظرفیت ثابت است، در حالی که در نسخه مشکل عمیق تخفیف، هر نوع کابل دارای ظرفیت نامحدود است، اما هزینه متغیر وابسته به ترافیک علاوه بر هزینه به هزینه راه اندازی ثابت آن. ما اولین الگوریتم تقریبی ثابت برای این مشکلات را با استفاده از تکنیک های مختلف الگوریتم و تحلیلی استخراج می کنیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
الگوریتم تقسیم ترکیبی برای مشکلات خرید محل اتصال در محل خرید
چکیده انگلیسی
In this paper, we introduce and analyze two fundamental versions of these problems. In the Buy-at-Bulk version of the problem, each access cable type has a fixed setup cost and a fixed capacity, whereas in the Deep-Discount problem version, each cable type has unlimited capacity but a traffic-dependent variable cost in addition to its fixed setup cost. We derive the first constant-factor approximation algorithms for these problems, using different algorithmic and analytical techniques.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 213, 20 November 2016, Pages 34-46
نویسندگان
, ,