Krivine diffusions attain the Goemans--Williamson approximation ratio

2019/06/25 by Ronen Eldan, Eldan, Ronen, Assaf Naor +1 · 7 citations
Computer Science · Mathematics · Physics and Astronomy · #Brownian motion #Combinatorics #Computer science #Data Structures and Algorithms (cs.DS) #Epistemology #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Mathematical economics #Mathematics #Philosophy #Physics #Rounding #Simple (philosophy) #Statistical physics #Statistics #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #cs.DS

paper · pdf · doi:10.48550/arxiv.1906.10615

published in arXiv (Cornell University) (Cornell University)

arxiv created 2019/06/25 · openalex publication_date 2019/06/25 · arxiv updated 2019/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Answering a question of Abbasi-Zadeh, Bansal, Guruganesh, Nikolov, Schwartz and Singh (2018), we prove the existence of a slowed-down sticky Brownian motion whose induced rounding for MAXCUT attains the Goemans--Williamson approximation ratio. This is an especially simple particular case of the general rounding framework of Krivine diffusions that we investigate elsewhere.

Citations

• On the power of unique 2-prover 1-round games

Related

• Beyond Wentzell-Freidlin: semi-deterministic approximations for diffusions with small noise and a repulsive critical boundary point
• The Bethe Ansatz for Sticky Brownian Motions
• Exact Small Time Equivalent for the density of the Circular Langevin Diffusion
• On oscillating sticky Brownian motion
• On the gradient dynamics associated with wetting models