Image de couverture de livre

Solving the Correlation Cluster LP in Sublinear Time

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Cao, Nairen, Cohen-Addad, Vincent, Li, Shi, Lee, Euiwoong, Lolck, David Rasmussen, Newman, Alantha, Thorup, Mikkel, Vogl, Lukas, Yan, Shuyi, Zhang, Hanwen
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Static to Dynamic Correlation Clustering
par: Cao, Nairen, et autres
Publié: (2025)

Understanding the Cluster LP for Correlation Clustering
par: Cao, Nairen, et autres
Publié: (2024)

Combinatorial Correlation Clustering
par: Cohen-Addad, Vincent, et autres
Publié: (2024)

Pivot based correlation clustering in the presence of good clusters
par: Lolck, David Rasmussen, et autres
Publié: (2026)

Dynamic Correlation Clustering in Sublinear Update Time
par: Cohen-Addad, Vincent, et autres
Publié: (2024)

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
par: Lee, Dahoon, et autres
Publié: (2025)

Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering
par: Cao, Nairen, et autres
Publié: (2024)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
par: Cohen-Addad, Vincent, et autres
Publié: (2022)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
par: Goranci, Gramoz, et autres
Publié: (2023)

A Faster Algorithm for Constrained Correlation Clustering
par: Fischer, Nick, et autres
Publié: (2025)

Coloring tournaments with few colors: Algorithms and complexity
par: Klingelhoefer, Felix, et autres
Publié: (2023)

Correlation Clustering Beyond the Pivot Algorithm
par: Behnezhad, Soheil, et autres
Publié: (2024)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

Instance-Optimality in PageRank Computation
par: Thorup, Mikkel, et autres
Publié: (2025)

Connectivity augmentation is fixed-parameter tractable
par: Korhonen, Tuukka, et autres
Publié: (2026)

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
par: Jin, Wenyu, et autres
Publié: (2024)

Improved linearly ordered colorings of hypergraphs via SDP rounding
par: Louis, Anand, et autres
Publié: (2024)

An Improved Greedy Approximation for (Metric) $k$-Means
par: Charikar, Moses, et autres
Publié: (2026)

Estimating Random-Walk Probabilities in Directed Graphs
par: Bertram, Christian, et autres
Publié: (2025)

Min-Max Correlation Clustering via Neighborhood Similarity
par: Cao, Nairen, et autres
Publié: (2025)

Distributed Algorithms for Euclidean Clustering
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
par: Fan, Chenglin, et autres
Publié: (2025)

On Solving Linear Systems in Sublinear Time
par: Andoni, Alexandr, et autres
Publié: (2018)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
par: Anand, Aditya, et autres
Publié: (2025)

Max-Cut with $ε$-Accurate Predictions
par: Cohen-Addad, Vincent, et autres
Publié: (2024)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

Fair Clustering in the Sliding Window Model
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
par: Kwok, Tsz Chiu, et autres
Publié: (2025)

Hardness and Approximation for Coloring Digraphs
par: Chalermsook, Parinya, et autres
Publié: (2026)

PageRank Centrality in Directed Graphs with Bounded In-Degree
par: Thorup, Mikkel, et autres
Publié: (2025)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
par: Narayanan, Shyam, et autres
Publié: (2024)

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
par: Cohen-Addad, Vincent, et autres
Publié: (2024)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
par: Huang, Shang-En, et autres
Publié: (2016)

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
par: Kacham, Praneeth, et autres
Publié: (2023)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

A Scalable Algorithm for Individually Fair K-means Clustering
par: Bateni, MohammadHossein, et autres
Publié: (2024)

Sublinear Spectral Clustering Oracle with Little Memory
par: Shen, Ranran, et autres
Publié: (2026)