کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427633 | 686533 | 2012 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Lower bounds for randomized algorithms for online chain partitioning
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We prove that the randomized competitive ratio of online chain partitioning of posets equals the deterministic competitive ratio.
► We consider performance of randomized algorithms for online chain partitioning of posets.
► We construct a set of partial orders that are hard instances for randomized algorithms.
► We prove that known lower bounds for deterministic algorithms hold for randomized algorithms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 112, Issues 17–18, 30 September 2012, Pages 663–666
Journal: Information Processing Letters - Volume 112, Issues 17–18, 30 September 2012, Pages 663–666
نویسندگان
Claire Mathieu, Olga Ohrimenko,