Semidefinite Programming Based Algorithms for the Ratio Cut Problem

In this paper we analyze a known relaxation for the Ratio Cut Problem based on positive semidefinite constraints and present a branch and bound algorithm and heuristics based on this relaxation. The relaxation and the algorithms were tested on small and moderate sized instances. The relaxation leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances and the best heuristics obtained optimum or almost optimum solutions for all tested instances. We prove interesting characteristics for each one of these heuristics. We also compared the semidefinite based branch and bound algorithm with a commercial integer programming solver.

2005