@techreport{TR-IC-05-32,
  number = {IC-05-32},
  author = {Luis A. A. Meira and Flávio Miyazawa},
  title = {Semidefinite Programming Based Algorithms for the
           Ratio Cut Problem},
  month = {December},
  year = {2005}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 23 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       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.
  }
}