Buchumschlag

Understanding the Cluster LP for Correlation Clustering

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Cao, Nairen, Cohen-Addad, Vincent, Lee, Euiwoong, Li, Shi, Newman, Alantha, Vogl, Lukas
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Solving the Correlation Cluster LP in Sublinear Time
von: Cao, Nairen, et al.
Veröffentlicht: (2025)

Static to Dynamic Correlation Clustering
von: Cao, Nairen, et al.
Veröffentlicht: (2025)

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
von: Lee, Dahoon, et al.
Veröffentlicht: (2025)

Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering
von: Cao, Nairen, et al.
Veröffentlicht: (2024)

Correlation Clustering Beyond the Pivot Algorithm
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

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

Combinatorial Correlation Clustering
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
von: Fan, Chenglin, et al.
Veröffentlicht: (2025)

Dynamic Correlation Clustering in Sublinear Update Time
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

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

Distributed Algorithms for Euclidean Clustering
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Coloring tournaments with few colors: Algorithms and complexity
von: Klingelhoefer, Felix, et al.
Veröffentlicht: (2023)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

Min-Max Correlation Clustering via Neighborhood Similarity
von: Cao, Nairen, et al.
Veröffentlicht: (2025)

Fair Clustering in the Sliding Window Model
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

An Improved Greedy Approximation for (Metric) $k$-Means
von: Charikar, Moses, et al.
Veröffentlicht: (2026)

Improved linearly ordered colorings of hypergraphs via SDP rounding
von: Louis, Anand, et al.
Veröffentlicht: (2024)

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

Max-Cut with $ε$-Accurate Predictions
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

Clustering with Non-adaptive Subset Queries
von: Black, Hadley, et al.
Veröffentlicht: (2024)

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

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

A Scalable Algorithm for Individually Fair K-means Clustering
von: Bateni, MohammadHossein, et al.
Veröffentlicht: (2024)

Hardness and Approximation for Coloring Digraphs
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2026)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Separating $k$-Median from the Supplier Version
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Facility Location on High-dimensional Euclidean Spaces
von: Lee, Euiwoong, et al.
Veröffentlicht: (2025)

Matroid-Based TSP Rounding for Half-Integral Solutions
von: Gupta, Anupam, et al.
Veröffentlicht: (2021)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
von: Axiotis, Kyriakos, et al.
Veröffentlicht: (2024)

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
von: Davies, Sami, et al.
Veröffentlicht: (2023)

Combinatorial Optimization using Comparison Oracles
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

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

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
von: Bansal, Nikhil, et al.
Veröffentlicht: (2024)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
von: Bansal, Nikhil, et al.
Veröffentlicht: (2026)

Approximating Small Sparse Cuts
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
von: Anand, Aditya, et al.
Veröffentlicht: (2025)

Cluster Vertex Deletion on Chordal Graphs
von: Cao, Yixin, et al.
Veröffentlicht: (2026)

Learning-Augmented Streaming Algorithms for Correlation Clustering
von: Dong, Yinhao, et al.
Veröffentlicht: (2025)