Cover Image

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fan, Chenglin, Lee, Dahoon, Lee, Euiwoong
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

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

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
by: Bansal, Nikhil, et al.
Published: (2026)

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

Optimal Learning-Augmented Algorithm for Online Bidding
by: Lee, Changyeol, et al.
Published: (2026)

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

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

Approximating Small Sparse Cuts
by: Anand, Aditya, et al.
Published: (2024)

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

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)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
by: Anand, Aditya, et al.
Published: (2025)

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

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

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

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
by: Ghoshal, Suprovat, et al.
Published: (2026)

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

Clustering with Non-adaptive Subset Queries
by: Black, Hadley, et al.
Published: (2024)

Improved Approximation Algorithms for Relational Clustering
by: Esmailpour, Aryan, et al.
Published: (2024)

Max Cut with Small-Dimensional SDP Solutions
by: Chang, Hsien-Chih, et al.
Published: (2026)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
by: Zhao, Jingyang, et al.
Published: (2025)

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

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
by: DeHaan, Ian, et al.
Published: (2025)

On Approximability of $\ell_2^2$ Min-Sum Clustering
by: S., Karthik C., et al.
Published: (2024)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

Learning Augmented Graph $k$-Clustering
by: Fan, Chenglin, et al.
Published: (2025)

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

Chromatic correlation clustering via cluster LP
by: Abbasi, Fateme, et al.
Published: (2025)

Unbreakable Decomposition in Close-to-Linear Time
by: Anand, Aditya, et al.
Published: (2024)

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
by: Ahn, Jungho, et al.
Published: (2025)

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

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

Improved Additive Approximation Algorithms for APSP
by: Jin, Ce, et al.
Published: (2025)

A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances
by: Dinitz, Michael, et al.
Published: (2025)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

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

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Improved Approximation Algorithms for Three-Dimensional Knapsack
by: Jansen, Klaus, et al.
Published: (2025)

Improved Approximation Algorithm for Maximum Balanced Biclique
by: Manurangsi, Pasin
Published: (2026)

An Improved Approximation Algorithm for Metric Triangle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)