LP—Relaxations for the Edge—Weighted Subclique Problem
Ulrich Faigle, R. Garbe, K. Heerink, Boris Spieker · 1994
We investigate the problem of finding the best subclique of a given size in a complete edge-weighted graph. This problem was formulated by Späth [S 85], who reports numerical results indicating that simple exchange heuristics perform very well on the problem. On the other hand, our problem is closely related to the well-studied clique partition problem (cf. [FSS 87], [W 86], [GW 89]), for which cutting plane algorithms appear to be quite succesfuland give tight bounds on the quality of heuristic solutions. Indeed, our problem is a partition problem where exactly one non-trivial block of a given size is allowed.