A Complex Semidefinite Programming Rounding Approximation Algorithm for the Balanced Max-3-Uncut Problem

摘要

In this paper, we consider the balanced Max-3-Uncut problem which has several applications in the design of VLSI circuits. We propose a complex discrete linear program for the balanced Max-3-Uncut problem. Applying the complex semidefinite programming rounding technique, we present a 0.3456-approximation algorithm by further integrating a greedy swapping process after the rounding step. One ingredient in our analysis different from previous work for the traditional Max-3-Cut is the introduction and analysis of a bivariate function rather than a univariate function.