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 and claimed that it achieves an expected ratio of 89/169 (1 - ∈) for any constant ∈ > 0. However, their analysis was flawed. We present a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio very close to their claimed expected ratio.