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 43 83 ( 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 .
approximation algorithms maximum triangle packing randomized algorithms maximum-weight b b -matching b b b b b