Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418834 | Discrete Applied Mathematics | 2009 | 7 Pages |
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 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zhi-Zhong Chen, Ruka Tanahashi, Lusheng Wang,