Max-Cut via Kuramoto-Type Oscillators

DOI10.1137/21m1432211arXiv2102.04931OpenAlexW3127724154MaRDI QIDQ6168211

Stefan Steinerberger

Publication date: 10 July 2023

Published in: SIAM Journal on Applied Dynamical Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.04931

zbMATH Keywords

maximum cutrandomized roundingKuramoto oscillator\textsc{Max-Cut}

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Graph theory (including graph drawing) in computer science (68R10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Synchronization in complex networks of phase oscillators: a survey
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• OIM: oscillator-based Ising machines for solving combinatorial optimisation problems
• Local minima and convergence in low-rank semidefinite programming
• Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
• There is no non-zero stable fixed point for dense networks in the homogeneous Kuramoto model
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Gadgets, Approximation, and Linear Programming
• Sufficiently dense Kuramoto networks are globally synchronizing
• Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs
• Dense networks that do not synchronize and sparse ones that do
• What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO
• Synchronization of Kuramoto oscillators in dense networks
• Synchronization in complex oscillator networks and smart grids
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

This page was built for publication: Max-Cut via Kuramoto-Type Oscillators