Buchumschlag

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Lee, Dahoon, Fan, Chenglin, Lee, Euiwoong
Format:	Preprint
Veröffentlicht:	2025
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

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

Understanding the Cluster LP for Correlation Clustering
von: Cao, Nairen, et al.
Veröffentlicht: (2024)

Chromatic correlation clustering via cluster LP
von: Abbasi, Fateme, et al.
Veröffentlicht: (2025)

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)

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

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

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

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

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
von: Anand, Aditya, et al.
Veröffentlicht: (2025)

Optimal Learning-Augmented Algorithm for Online Bidding
von: Lee, Changyeol, et al.
Veröffentlicht: (2026)

On Approximability of $\ell_2^2$ Min-Sum Clustering
von: S., Karthik C., et al.
Veröffentlicht: (2024)

Improved Combinatorial Approximations for Weighted Correlation Clustering
von: Ostovari, Mojtaba, et al.
Veröffentlicht: (2023)

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

Learning Augmented Graph $k$-Clustering
von: Fan, Chenglin, et al.
Veröffentlicht: (2025)

Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs
von: Amir, Amihood, et al.
Veröffentlicht: (2024)

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture
von: Björklund, Andreas, et al.
Veröffentlicht: (2024)

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

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
von: Zhou, Jianqi, et al.
Veröffentlicht: (2025)

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
von: Goranci, Gramoz, et al.
Veröffentlicht: (2025)

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

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

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

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

Max Cut with Small-Dimensional SDP Solutions
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2026)

Combinatorial Correlation Clustering
von: Cohen-Addad, Vincent, 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)

Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
von: Friggstad, Zachary, et al.
Veröffentlicht: (2025)

Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach
von: Lee, Changyeol, et al.
Veröffentlicht: (2025)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
von: German, Samuel
Veröffentlicht: (2026)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
von: DeHaan, Ian, et al.
Veröffentlicht: (2025)

Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics
von: An, Hyung-Chan, et al.
Veröffentlicht: (2025)

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

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

On the Parameterized Approximability of (Mergeable) Sum of Radii Clustering
von: Gadekar, Ameet
Veröffentlicht: (2026)

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

A Faster Algorithm for Constrained Correlation Clustering
von: Fischer, Nick, et al.
Veröffentlicht: (2025)

Fair Correlation Clustering Meets Graph Parameters
von: Blaha, Johannes, et al.
Veröffentlicht: (2026)

Unbreakable Decomposition in Close-to-Linear Time
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
von: Ahn, Jungho, et al.
Veröffentlicht: (2025)