Establishes Ω(n/ε²) query lower bounds for approximating correlation clustering cost and partitions under memory constraints in adjacency-matrix and general graph models.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC) , pages =
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
verdicts
UNVERDICTED 3representative citing papers
Proves ∃R-hardness of approximating MAX-ETR-INV to within a constant factor and gives polynomial-time 8-factor and nondeterministic 2-factor approximation algorithms.
Incremental (1-ε)-approximate s-t max-flow algorithm achieving Õ(m + n F*/ε) total update time, first with polylog amortized updates for dense 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.
-
Probabilistically checkable proofs for the Existential Theory of the Reals
Proves ∃R-hardness of approximating MAX-ETR-INV to within a constant factor and gives polynomial-time 8-factor and nondeterministic 2-factor approximation algorithms.
-
Incremental Approximate Maximum Flow via Residual Graph Sparsification
Incremental (1-ε)-approximate s-t max-flow algorithm achieving Õ(m + n F*/ε) total update time, first with polylog amortized updates for dense graphs.