{"ID":2831312,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.08852","arxiv_id":"2512.08852","title":"Speeding up the Goemans-Williamson randomized procedure by difference-of-convex optimization","abstract":"We present a novel approach to accelerate the Goemans-Williamson (GW) randomized rounding procedure for quadratic unconstrained binary optimization (QUBO) problems. Instead of solving the conventional semi-definite programming (SDP) relaxation, which is computationally expensive, we employ a difference-of-convex (DC) optimization framework to efficiently approximate the SDP solution. The DC optimization produces candidate vectors that are then used within the GW randomized rounding scheme to generate high-quality binary solutions. Furthermore, we perform direct expectation minimization over manifolds of matrices with limited rank to further enhance the solution quality. Our method is benchmarked on real-world QUBO instances, including inverse kinematics problems, and compared against state-of-the-art solvers, such as quantum-inspired algorithms, demonstrating competitive approximation guarantees alongside substantial computational gains.","short_abstract":"We present a novel approach to accelerate the Goemans-Williamson (GW) randomized rounding procedure for quadratic unconstrained binary optimization (QUBO) problems. Instead of solving the conventional semi-definite programming (SDP) relaxation, which is computationally expensive, we employ a difference-of-convex (DC) o...","url_abs":"https://arxiv.org/abs/2512.08852","url_pdf":"https://arxiv.org/pdf/2512.08852v1","authors":"[\"Hadi Salloum\",\"Roland Hildebrand\",\"Nhat Trung Nguyen\",\"Vitali Pirau\",\"Amer Al Badr\",\"Mohammad Alkousa\",\"Alexander Gasnikov\"]","published":"2025-12-09T17:46:56Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}