Technical Report Number
Given a complete graph with nonnegative edge weights satisfying the triangle inequality and a positive integer p, the remote-clique problem is to find a subset of p vertices having a maximum-weight induced subgraph. A simple greedy algorithm for the problem has been shown to have an approximation ratio of 4, but a tight example has not been provided. In this paper, we use the technique of factor revealing linear programs to prove that this algorithm actually achieves an approximation ratio of 2, matching the best-known ratio for the problem. The greedy algorithm's running time of O(pn) makes it the fastest known 2-approximation for the remote-clique problem.
Birnbaum, Benjamin E. and Goldman, Kenneth J., "An Improved Analysis for a Greedy Remote-Clique Algorithm using Factor-Revealing LPs" Report Number: WUCSE-2006-3 (2006). All Computer Science and Engineering Research.
Permanent URL: http://dx.doi.org/10.7936/K7XP7346