Cover Image

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Veldt, Nate
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the tractability and approximability of non-submodular cardinality-based $s$-$t$ cut problems in hypergraphs
by: Bengali, Vedangi, et al.
Published: (2024)

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
by: Crane, Alex, et al.
Published: (2025)

Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized Methods
by: Huang, Yufan, et al.
Published: (2023)

Bounding $\varepsilon$-scatter dimension via metric sparsity
by: Bourneuf, Romain, et al.
Published: (2024)

Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
by: Veldt, Nate, et al.
Published: (2025)

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
by: Davies, Sami, et al.
Published: (2023)

Fast approximation algorithms for the 1-median problem on real-world large graphs
by: Ueta, Keisuke, et al.
Published: (2025)

Approximating Submodular Matroid-Constrained Partitioning
by: Bérczi, Kristóf, et al.
Published: (2025)

Hop-Constrained Metric Embeddings and their Applications
by: Filtser, Arnold
Published: (2021)

An approximation algorithm for Maximum DiCut vs. Cut
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

A Nonparametric Framework for Online Stochastic Matching with Correlated Arrivals
by: Aouad, Ali, et al.
Published: (2022)

Fast Makespan Minimization via Short ILPs
by: Hermelin, Danny, et al.
Published: (2026)

Improved Streaming Algorithm for Fair $k$-Center Clustering
by: Guo, Longkun, et al.
Published: (2025)

Parameterized Algorithms for Balanced Cluster Edge Modification Problems
by: Madathil, Jayakrishnan, et al.
Published: (2024)

Total Domination, Separated Clusters, CD-Coloring: Algorithms and Hardness
by: Antony, Dhanyamol, et al.
Published: (2023)

Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
by: Jordon, Addie, et al.
Published: (2025)

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
by: Gaikwad, Ajinkya
Published: (2025)

A logarithmic approximation of linearly ordered colourings
by: Håstad, Johan, et al.
Published: (2024)

Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms
by: Davies, Sami, et al.
Published: (2025)

Deterministic approximation for the volume of the truncated fractional matching polytope
by: Guo, Heng, et al.
Published: (2024)

Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks
by: Hsieh, Jun-Ting, et al.
Published: (2026)

A column generation algorithm for finding co-3-plexes in chordal graphs
by: Dupont-Bouillard, Alexandre
Published: (2026)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
by: Shakeri, Heman, et al.
Published: (2025)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
by: Bencs, Ferenc, et al.
Published: (2024)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
by: de Montgolfier, Fabien, et al.
Published: (2025)

Simple Compact Monotone Tree Drawings
by: Oikonomou, Anargyros, et al.
Published: (2017)

A survey of Chernoff and Hoeffding bounds
by: Gerbessiotis, Alexandros V.
Published: (2025)

A Parameterized Perspective on Uniquely Restricted Matchings
by: Chaudhary, Juhi, et al.
Published: (2025)

A Constant-Factor Approximation for Directed Latency
by: Blauth, Jannis, et al.
Published: (2025)

A Tale of Santa Claus, Hypergraphs and Matroids
by: Davies, Sami, et al.
Published: (2018)

A note on approximating the average degree of bounded arboricity graphs
by: Eden, Talya, et al.
Published: (2026)

A 4-approximation algorithm for min max correlation clustering
by: Heidrich, Holger, et al.
Published: (2023)

Sequential testing problem: A follow-up review
by: Ünlüyurt, Tonguç
Published: (2025)

A Unified Approach to Minimizing Symmetric Submodular Functions
by: Iwata, Satoru, et al.
Published: (2026)

A Finer View of the Parameterized Landscape of Labeled Graph Contractions
by: Mathur, Yashaswini, et al.
Published: (2025)

A polynomial kernel for vertex deletion into bipartite permutation graphs
by: Derbisz, Jan
Published: (2021)

A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
by: Harada, Tsubasa, et al.
Published: (2024)

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
by: Abboud, Amir, et al.
Published: (2025)

A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
by: Liang, Wei, et al.
Published: (2024)