An approximation algorithm for maximum triangle packing

We present a randomized (89169-ε)-approximation algorithm for the weighted maximum triangle packing problem, for any given ε>0ε>0. This is the first algorithm for this problem whose performance guarantee is better than 12. The algorithm also improves the best-known approximation bound for the maximum 2-edge path packing problem.