کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1143144 | 957180 | 2007 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A simpler and better derandomization of an approximation algorithm for single source rent-or-buy A simpler and better derandomization of an approximation algorithm for single source rent-or-buy](/preview/png/1143144.png)
چکیده انگلیسی
We present a very simple way of derandomizing the algorithm proposed by Gupta, Kumar and Roughgarden for single source rent-or-buy by using the method of conditional expectation. Using the improved analysis of Eisenbrand, Grandoni and Rothvoß, our derandomized algorithm has an approximation guarantee of 3.28.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 35, Issue 6, November 2007, Pages 707–712
Journal: Operations Research Letters - Volume 35, Issue 6, November 2007, Pages 707–712
نویسندگان
David P. Williamson, Anke van Zuylen,