کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418834 | 681720 | 2009 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An improved randomized approximation algorithm for maximum triangle packing
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm that achieves an expected ratio of 4383(1−ϵ)(≈0.518(1−ϵ)) for any constant ϵ>0ϵ>0. By modifying their algorithm, we obtain a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio of 0.5257(1−ϵ)0.5257(1−ϵ) for any constant ϵ>0ϵ>0.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1640–1646
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1640–1646
نویسندگان
Zhi-Zhong Chen, Ruka Tanahashi, Lusheng Wang,