A Cutting Plane SDP Method for Maxcut Problems
Download the talk,
in pdf format.
Authors:
Kartik Krishnan and
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
kartis@rpi.edu and
mitchj@rpi.edu
August 3, 2002.
Given at the
McMaster Optimization
Conference, 2002
Abstract:
We investigate solution of the maximum cut problem using a semidefinite
programming approach. The dual of the well-known SDP relaxation of maxcut
is formulated as a semi-infinite linear programming problem, which is
solved with a cutting plane algorithm. Cutting planes based on the
polyhedral theory of the maxcut problem are then added to the primal
problem in order to improve the SDP relaxation. Computational results
are provided.
Download the talk,
in pdf format.
Return to my list of talks.