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 δδ-approximation algorithm, then the maximum edge clique partitioning problem (Max-ECP) can be solved by a polynomial time 2(pδ−1)p−1-approximation algorithm for any fixed integer p≥2p≥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.