Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871335 | Discrete Applied Mathematics | 2018 | 23 Pages |
Abstract
Combining this algorithm with a previously known approximation algorithm for the 3-Set Packing problem, we obtain a .6-approximation algorithm for the problem of partitioning a {0,1}-edge-weighted graph into k vertex disjoint triangles of maximum total weight. The best known approximation algorithm for general weights is due to Chen and Tanahashi (2009) and achieves an approximation ratio of .5257.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Amotz Bar-Noy, David Peleg, George Rabanca, Ivo Vigan,