Cover Image

Estimating Correlation Clustering Cost in Node-Arrival Stream

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Liu, Kaiwen, Villalobos, Seba Daniela, Zhang, Qin
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity
by: Liu, Kaiwen, et al.
Published: (2026)

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
by: Buchbinder, Niv, et al.
Published: (2026)

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
by: Peng, Pan, et al.
Published: (2025)

Learning-Augmented Streaming Algorithms for Correlation Clustering
by: Dong, Yinhao, et al.
Published: (2025)

Combinatorial Correlation Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Understanding the Cluster LP for Correlation Clustering
by: Cao, Nairen, et al.
Published: (2024)

Static to Dynamic Correlation Clustering
by: Cao, Nairen, et al.
Published: (2025)

A Nonparametric Framework for Online Stochastic Matching with Correlated Arrivals
by: Aouad, Ali, et al.
Published: (2022)

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
by: Zhou, Jianqi, et al.
Published: (2025)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
by: Jiang, Tianle, et al.
Published: (2024)

Solving the Correlation Cluster LP in Sublinear Time
by: Cao, Nairen, et al.
Published: (2025)

Correlation Clustering Beyond the Pivot Algorithm
by: Behnezhad, Soheil, et al.
Published: (2024)

Estimating Diffusion Degree on Graph Streams
by: Gore, Vinit Ramesh, et al.
Published: (2024)

Online Multi-level Aggregation with Delays and Stochastic Arrivals
by: Mari, Mathieu, et al.
Published: (2024)

Online Rounding for Set Cover under Subset Arrivals
by: Byrka, Jarosław, et al.
Published: (2025)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Fair Correlation Clustering Meets Graph Parameters
by: Blaha, Johannes, et al.
Published: (2026)

Improved Combinatorial Approximations for Weighted Correlation Clustering
by: Ostovari, Mojtaba, et al.
Published: (2023)

A Faster Algorithm for Constrained Correlation Clustering
by: Fischer, Nick, et al.
Published: (2025)

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
by: Lee, Dahoon, et al.
Published: (2025)

Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering
by: Adriaens, Florian, et al.
Published: (2026)

Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering
by: Cao, Nairen, et al.
Published: (2024)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
by: Fan, Chenglin, et al.
Published: (2025)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
by: Assadi, Sepehr, et al.
Published: (2025)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
by: Dalirrooyfard, Mina, et al.
Published: (2024)

Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum
by: Sun, Enze, et al.
Published: (2025)

Multilayer Correlation Clustering
by: Miyauchi, Atsushi, et al.
Published: (2024)

Error Correction for Message Streams
by: Gupta, Meghal, et al.
Published: (2023)

Node ranking in labeled networks
by: Arachchi, Chamalee Wickrama, et al.
Published: (2025)

Improved Streaming Edge Coloring
by: Chechik, Shiri, et al.
Published: (2025)

A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams
by: Cambus, Mélanie, et al.
Published: (2022)

QSketch: An Efficient Sketch for Weighted Cardinality Estimation in Streams
by: Qi, Yiyan, et al.
Published: (2024)

Faster Deterministic Streaming Vertex Coloring
by: Chechik, Shiri, et al.
Published: (2026)

Node-Weighted Multicut in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2026)

RCM++:Reverse Cuthill-McKee ordering with Bi-Criteria Node Finder
by: Hou, JiaJun, et al.
Published: (2024)

Streaming Edge Coloring with Subquadratic Palette Size
by: Chechik, Shiri, et al.
Published: (2023)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
by: Chen, Yu, et al.
Published: (2026)

Lower Bounds on $0$-Extension with Steiner Nodes
by: Chen, Yu, et al.
Published: (2024)

Adaptive Multi-Round Allocation with Stochastic Arrivals
by: Pan, Yuqi, et al.
Published: (2026)

Improved Streaming Algorithm for Fair $k$-Center Clustering
by: Guo, Longkun, et al.
Published: (2025)