| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1141751 | Discrete Optimization | 2012 | 4 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Abraham P. Punnen, Ruonan Zhang,