Establishes Ω(n/ε²) query lower bounds for approximating correlation clustering cost and partitions under memory constraints in adjacency-matrix and general graph models.
Approximation, Randomization, and Combinatorial Optimization
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
representative citing papers
Streaming max-cut requires Ω(n) space for dense graphs but Ω(n log(ε² n)/ε²) space for graphs with Θ(n/ε²) edges when outputting the cut, with matching upper bounds for dense case and similar separations for densest subgraph.
A two-pass sublinear-space streaming algorithm achieves (1/2-ε)-approximation for Max-DICUT on unbounded-degree graphs.
citing papers explorer
-
Query Lower Bounds for Correlation Clustering under Memory Constraints
Establishes Ω(n/ε²) query lower bounds for approximating correlation clustering cost and partitions under memory constraints in adjacency-matrix and general graph models.
-
Streaming Complexity Separations for Dense and Sparse Graphs
Streaming max-cut requires Ω(n) space for dense graphs but Ω(n log(ε² n)/ε²) space for graphs with Θ(n/ε²) edges when outputting the cut, with matching upper bounds for dense case and similar separations for densest subgraph.
-
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.