Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem

In this note, we show that if the maximum clique problem can be solved by a polynomial time $\delta$ ‐approximation algorithm, then the maximum edge clique partitioning problem (Max‐ECP) can be solved by a polynomial time $\frac{2(p\delta ‐1)}{p‐1}$ ‐approximation algorithm for any fixed integer $p\ge 2$ . This improves the best known bound on the performance ratio of an approximation algorithm for Max‐ECP problem and also corrects an error in an earlier work on the topic.