Buchumschlag

A 4-approximation algorithm for min max correlation clustering

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Heidrich, Holger, Irmai, Jannik, Andres, Bjoern
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Data Structures and Algorithms Discrete Mathematics Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Partial Optimality in the Preordering Problem
von: Stein, David, et al.
Veröffentlicht: (2026)

Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis
von: Sharman, Bharat, et al.
Veröffentlicht: (2025)

An approximation algorithm for Maximum DiCut vs. Cut
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

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

Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
von: Tukan, Murad, et al.
Veröffentlicht: (2024)

Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms
von: Davies, Sami, et al.
Veröffentlicht: (2025)

Exact Causal Attention with 10% Fewer Operations
von: Rybin, Dmitry, et al.
Veröffentlicht: (2025)

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
von: Crane, Alex, et al.
Veröffentlicht: (2025)

Graph Inference with Effective Resistance Queries
von: Bennett, Huck, et al.
Veröffentlicht: (2025)

Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
von: Veldt, Nate, et al.
Veröffentlicht: (2025)

Worst-case Error Bounds for Online Learning of Smooth Functions
von: Xie, Weian
Veröffentlicht: (2025)

Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization
von: Chen, Yixin, et al.
Veröffentlicht: (2024)

Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations
von: He, Xi
Veröffentlicht: (2025)

Breaking Hard Isomorphism Benchmarks with DRESS
von: Velilla, Eduar Castrillo
Veröffentlicht: (2026)

An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem
von: Xue, Jinghui, et al.
Veröffentlicht: (2024)

Optimal hypersurface decision trees
von: He, Xi
Veröffentlicht: (2025)

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
von: Veldt, Nate
Veröffentlicht: (2025)

A column generation algorithm for finding co-3-plexes in chordal graphs
von: Dupont-Bouillard, Alexandre
Veröffentlicht: (2026)

Approximation algorithms for non-sequential star packing problems
von: Hu, Mengyuan, et al.
Veröffentlicht: (2024)

Moderately beyond clique-width: reduced component max-leaf and related parameters
von: Bonnet, Édouard, et al.
Veröffentlicht: (2026)

Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness
von: Zhang, Bohang, et al.
Veröffentlicht: (2024)

Solving the List Coloring Problem through a Branch-and-Price algorithm
von: Lucci, Mauro, et al.
Veröffentlicht: (2023)

Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice
von: Tan, Jingjing
Veröffentlicht: (2024)

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
von: Foucaud, Florent, et al.
Veröffentlicht: (2025)

Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach
von: Liao, Meihao, et al.
Veröffentlicht: (2025)

An algorithm with a delay of $\mathcal{O}(kΔ)$ for enumerating connected induced subgraphs of size $k$
von: Xiao, Chenglong, et al.
Veröffentlicht: (2024)

A logarithmic approximation of linearly ordered colourings
von: Håstad, Johan, et al.
Veröffentlicht: (2024)

Box Facets and Cut Facets of Lifted Multicut Polytopes
von: Naumann, Lucas Fabian, et al.
Veröffentlicht: (2024)

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
von: Abboud, Amir, et al.
Veröffentlicht: (2025)

Deterministic approximation for the volume of the truncated fractional matching polytope
von: Guo, Heng, et al.
Veröffentlicht: (2024)

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
von: Bernshteyn, Anton, et al.
Veröffentlicht: (2024)

Parameterised algorithms for temporally satisfying reconfiguration problems
von: Davot, Tom, et al.
Veröffentlicht: (2025)

A Unified Approach to Submodular Maximization Under Noise
von: Bhawalkar, Kshipra, et al.
Veröffentlicht: (2025)

Efficient algorithms for the Potts model on small-set expanders
von: Carlson, Charles, et al.
Veröffentlicht: (2020)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
von: Deák, Bence, et al.
Veröffentlicht: (2026)

Generalising the maximum independent set algorithm via Boolean networks
von: Gadouleau, Maximilien, et al.
Veröffentlicht: (2024)

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
von: Alecu, Bogdan, et al.
Veröffentlicht: (2024)

Barvinok's interpolation method meets Weitz's correlation decay approach
von: Bencs, Ferenc, et al.
Veröffentlicht: (2025)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2024)

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