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

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
نویسندگان
, , ,