کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875714 1441981 2018 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A new lower bound for the on-line coloring of intervals with bandwidth
ترجمه فارسی عنوان
محدودیت جدید برای رنگ آمیزی فواصل با پهنای باند آنلاین
کلمات کلیدی
رنگ آمیزی بر روی خط، نمودارهای فاصله، فواصل وزن،
ترجمه چکیده
رنگ آمیزی فاصله در خط و انواع آن مشکلات بزرگی ترکیبی با بسیاری از برنامه های کاربردی در توزیع شبکه، تخصیص منابع و برنامه ریزی شغلی است. در این مقاله، مرز پایینی جدید 4.1626 را برای ضریب رقابت نسبی برای رنگ آمیزی مجدد فواصل با پهنای باند ارائه می کنیم که مرز پایین ترین شناخته شده 247 را بهبود می بخشد. برای رنگ آمیزی فضای واحد با پهنای باند در خط، ما بهبود می یابیم. مرز پایین 1.831 تا 2.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
محدودیت جدید برای رنگ آمیزی فواصل با پهنای باند آنلاین
چکیده انگلیسی
The on-line interval coloring and its variants are important combinatorial problems with many applications in network multiplexing, resource allocation and job scheduling. In this paper we present a new lower bound of 4.1626 for the asymptotic competitive ratio for the on-line coloring of intervals with bandwidth which improves the best known lower bound of 247. For the on-line coloring of unit intervals with bandwidth we improve the lower bound of 1.831 to 2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 708, 17 January 2018, Pages 96-100
نویسندگان
,