arXiv Open Access 2019

Krivine diffusions attain the Goemans--Williamson approximation ratio

Ronen Eldan Assaf Naor

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DS

Penulis (2)

Ronen Eldan

Assaf Naor

Format Sitasi

APA MLA BibTeX

Eldan, R., Naor, A. (2019). Krivine diffusions attain the Goemans--Williamson approximation ratio. https://arxiv.org/abs/1906.10615

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2019
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓