Single-pass streaming algorithms for correlation clustering

DOI10.1137/1.9781611977554.CH33MaRDI QIDQ6538560zbMATH OpenFDO

Authors Soheil Behnezhad, Moses Charikar, W. Y. Ma, Li-Yang Tan

Publication date 14 May 2024

Full work available at URL https://doi.org/10.1137/1.9781611977554.CH33

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Correlation clustering in data streams
• A (3 + )-approximate correlation clustering algorithm in dynamic streams
• Sublinear time and space algorithms for correlation clustering via sparse-dense decompositions
• Better streaming algorithms for clustering problems

Cited in

(8)

• Sublinear time and space algorithms for correlation clustering via sparse-dense decompositions
• A (3 + )-approximate correlation clustering algorithm in dynamic streams
• Streaming edge coloring with asymptotically optimal colors
• A (3+)-approximate correlation clustering algorithm in dynamic streams
• New algorithms and lower bounds for streaming tournaments
• A faster algorithm for constrained correlation clustering
• Fitting tree metrics and ultrametrics in data streams
• 1.64-approximation for chromatic correlation clustering via chromatic cluster LP

This page was built for publication: Single-pass streaming algorithms for correlation clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6538560)