Article ID Journal Published Year Pages File Type
421050 Discrete Applied Mathematics 2006 9 Pages PDF
Abstract

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.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
An approximation algorithm for maximum triangle packing
Authors
, ,