Cover Image

Static to Dynamic Correlation Clustering

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cao, Nairen, Cohen-Addad, Vincent, Lee, Euiwoong, Li, Shi, Lolck, David Rasmussen, Newman, Alantha, Thorup, Mikkel, Vogl, Lukas, Yan, Shuyi, Zhang, Hanwen
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Pivot based correlation clustering in the presence of good clusters
by: Lolck, David Rasmussen, et al.
Published: (2026)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
by: Cohen-Addad, Vincent, et al.
Published: (2022)

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

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

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Dynamic Correlation Clustering in Sublinear Update Time
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Coloring tournaments with few colors: Algorithms and complexity
by: Klingelhoefer, Felix, et al.
Published: (2023)

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

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

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

An Improved Greedy Approximation for (Metric) $k$-Means
by: Charikar, Moses, et al.
Published: (2026)

Estimating Random-Walk Probabilities in Directed Graphs
by: Bertram, Christian, et al.
Published: (2025)

Instance-Optimality in PageRank Computation
by: Thorup, Mikkel, et al.
Published: (2025)

Connectivity augmentation is fixed-parameter tractable
by: Korhonen, Tuukka, et al.
Published: (2026)

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
by: Jin, Wenyu, et al.
Published: (2024)

Improved linearly ordered colorings of hypergraphs via SDP rounding
by: Louis, Anand, et al.
Published: (2024)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
by: Anand, Aditya, et al.
Published: (2025)

Max-Cut with $ε$-Accurate Predictions
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Min-Max Correlation Clustering via Neighborhood Similarity
by: Cao, Nairen, et al.
Published: (2025)

Distributed Algorithms for Euclidean Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2026)

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

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Fair Clustering in the Sliding Window Model
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

PageRank Centrality in Directed Graphs with Bounded In-Degree
by: Thorup, Mikkel, et al.
Published: (2025)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
by: Narayanan, Shyam, et al.
Published: (2024)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
by: Huang, Shang-En, et al.
Published: (2016)

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
by: Kacham, Praneeth, et al.
Published: (2023)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
by: Goranci, Gramoz, et al.
Published: (2023)

Facility Location on High-dimensional Euclidean Spaces
by: Lee, Euiwoong, et al.
Published: (2025)

Separating $k$-Median from the Supplier Version
by: Anand, Aditya, et al.
Published: (2024)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Combinatorial Optimization using Comparison Oracles
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
by: Cohen-Addad, Vincent, et al.
Published: (2025)

A Scalable Algorithm for Individually Fair K-means Clustering
by: Bateni, MohammadHossein, et al.
Published: (2024)

Matroid-Based TSP Rounding for Half-Integral Solutions
by: Gupta, Anupam, et al.
Published: (2021)