Krivine diffusions attain the Goemans-Williamson approximation ratio.
Ronen EldanAssaf NaorPublished in: CoRR (2019)
Keyphrases
- approximation ratio
- approximation algorithms
- np hard
- special case
- search algorithm
- greedy algorithm
- approximately optimal
- diffusion processes
- minimum cost
- vector valued
- greedy algorithms
- anisotropic diffusion
- brownian motion
- real time
- integer programming
- approximation guarantees
- lower bound
- computer vision
- machine learning