A two-pass sublinear-space streaming algorithm achieves (1/2-ε)-approximation for Max-DICUT on unbounded-degree graphs.
Title resolution pending
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
fields
cs.DS 3representative citing papers
Existence is proved of a slowed-down sticky Brownian motion that induces a MAXCUT rounding attaining the Goemans-Williamson approximation ratio.
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
citing papers explorer
-
Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
A two-pass sublinear-space streaming algorithm achieves (1/2-ε)-approximation for Max-DICUT on unbounded-degree graphs.
-
Krivine diffusions attain the Goemans--Williamson approximation ratio
Existence is proved of a slowed-down sticky Brownian motion that induces a MAXCUT rounding attaining the Goemans-Williamson approximation ratio.
-
Hardness and Approximation for Coloring Digraphs
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.