Title of article
An improved randomized approximation algorithm for maximum triangle packing
Author/Authors
Zhi-Zhong Chen، نويسنده , , Ruka Tanahashi، نويسنده , , Lusheng Wang، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2009
Pages
7
From page
1640
To page
1646
Abstract
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 image for any constant image. By modifying their algorithm, we obtain a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio of image for any constant image.
Keywords
Maximum triangle packing , Approximation algorithms , Randomized algorithms , Maximum-weight bb-matching
Journal title
Discrete Applied Mathematics
Serial Year
2009
Journal title
Discrete Applied Mathematics
Record number
887094
Link To Document