We present a deterministic dynamical framework for approximating the Max-Cut problem via a factorized semidefinite programming (SDP) formulation. Unlike classical approaches such as the Goemans–Williamson algorithm, which rely on solving an SDP followed by randomized rounding, our method operates entirely through iterative dynamics combining first-order updates with a minimal curvature estimator. The proposed dynamics provably escape saddle points without randomness, avoid suboptimal stationary solutions via instability mechanisms, and converge to near-optimal SDP solutions. We establish that the basin of attraction of near-optimal solutions has full measure, implying almost-sure convergence from generic initialization. Furthermore, we derive explicit bounds on the time required to enter this basin in terms of graph parameters, including degree and spectral gap. By coupling the resulting embedding with standard hyperplane rounding, we obtain approximation guarantees matching the Goemans–Williamson ratio up to a vanishing error term. This provides a fully dynamic and deterministic alternative to SDP-based Max-Cut approximation, with explicit convergence and performance guarantees. This version (V10) completes the foundational framework and establishes equivalence to the Goemans–Williamson approximation guarantee through a novel dynamical paradigm. This work introduces a deterministic alternative to SDP-based Max-Cut approximation, demonstrating that Goemans–Williamson-level guarantees can be achieved through adaptive dynamics without solving a convex relaxation. Future versions will explore improved rounding strategies and extensions beyond SDP-equivalent performance.
Alexandria Jordan Lee Robinson (Thu,) studied this question.