Clustering with qualitative information

Specifically, we demonstrate a factor 4 approximation for minimization on complete graphs, and a factor O(logn) approximation for general graphs. For the maximization version, a PTAS for complete graphs was shown by Bansal et al. (2002), we give a factor 0.7664 approximation for general graphs, noting that a PTAS is unlikely by proving APX-hardness. We also prove the APX-hardness of minimization on complete graphs.