Generalized Max-Cut and the Approximation Ratio

In this thesis, we formulate a new problem based on Max-Cut called Generalized Max-Cut. This problem requires a graph as input and two real numbers (a, b) where a > 0 and −a < b < a and outputs a number. The restriction on the pair (a, b) is to avoid trivializing the problem. We formulate a quadratic program for Generalized Max-Cut and relax it to a semi-definite program. Most algorithms in this thesis will require solving this semi-definite program. The main algorithm in this thesis is the 2-Dimensional Rounding algorithm, designed by Avidor and Zwick, with the restriction that the semi-definite program of the input graph must have 2-Dimensional solutions. This algorithm uses a factor of randomness, β ∈ [0, 1], that is dependent on the integer input to Generalized Max-Cut. We improve the performance of this algorithm by numerically finding better β.