Cover Image

Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Balmaseda, Vicente, Xu, Ying, Cao, Yixin, Veldt, Nate
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Machine Learning Social and Information Networks
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An Improved Combinatorial Algorithm for Edge-Colored Clustering in Hypergraphs
by: Han, Seongjune, et al.
Published: (2026)

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

Adaptive Local Clustering over Attributed Graphs
by: Zheng, Haoran, et al.
Published: (2025)

Efficient Approximate Temporal Triangle Counting in Streaming with Predictions
by: Venturin, Giorgio, et al.
Published: (2025)

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
by: Veldt, Nate
Published: (2025)

A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time
by: Shen, Ranran, et al.
Published: (2023)

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

Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs
by: Li, Zihao, et al.
Published: (2024)

Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
by: Veldt, Nate, et al.
Published: (2026)

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
by: Bhaskara, Aditya, et al.
Published: (2024)

inGRASS: Incremental Graph Spectral Sparsification via Low-Resistance-Diameter Decomposition
by: Aghdaei, Ali, et al.
Published: (2024)

Weighted Embeddings for Low-Dimensional Graph Representation
by: Bläsius, Thomas, et al.
Published: (2024)

Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control
by: Elahi, Sepehr, et al.
Published: (2025)

Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model
by: Feng, Weiming, et al.
Published: (2025)

Revisiting Information Cascades in Online Social Networks
by: Sidorov, Michael, et al.
Published: (2022)

Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity
by: Oettershagen, Lutz, et al.
Published: (2025)

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

Better and Simpler Lower Bounds for Differentially Private Statistical Estimation
by: Narayanan, Shyam
Published: (2023)

Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality
by: Li, Zihao, et al.
Published: (2024)

Cluster Vertex Deletion on Chordal Graphs
by: Cao, Yixin, et al.
Published: (2026)

Overlapping and Robust Edge-Colored Clustering in Hypergraphs
by: Crane, Alex, et al.
Published: (2023)

Node Similarities under Random Projections: Limits and Pathological Cases
by: Tadić, Tvrtko, et al.
Published: (2024)

HITSnDIFFs: From Truth Discovery to Ability Discovery by Recovering Matrices with the Consecutive Ones Property
by: Chen, Zixuan, et al.
Published: (2023)

Fast Percolation Centrality Approximation with Importance Sampling
by: Cruciani, Antonio, et al.
Published: (2025)

MANTRA: Temporal Betweenness Centrality Approximation through Sampling
by: Cruciani, Antonio
Published: (2023)

Overcoming Non-Submodularity: Towards Constant Approximation for Network Immunization
by: Srivastava, Ajitesh, et al.
Published: (2024)

Fast Approximate CoSimRanks via Random Projections
by: Yang, Renchi, et al.
Published: (2020)

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
by: Spaeh, Fabian, et al.
Published: (2025)

Approximation Algorithms for Combinatorial Optimization with Predictions
by: Antoniadis, Antonios, et al.
Published: (2024)

A Fully-dynamic Approximation Algorithm for Maximum Weight b-Matchings in Graphs
by: Brandt-Tumescheit, Fabian, et al.
Published: (2024)

Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic Approximation
by: Bläsius, Thomas, et al.
Published: (2024)

Locally Differentially Private Graph Clustering via the Power Iteration Method
by: Suppakitpaisarn, Vorapong, et al.
Published: (2025)

A Faster Generalized Two-Stage Approximate Top-K
by: Samaga, Yashas, et al.
Published: (2025)

Spectral Toolkit of Algorithms for Graphs: Technical Report (2)
by: Macgregor, Peter, et al.
Published: (2024)

A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation
by: Hashemi, Mohammad, et al.
Published: (2024)

Differential Privacy on Trust Graphs
by: Ghazi, Badih, et al.
Published: (2024)

An Efficient Streaming Algorithm for Approximating Graphlet Distributions
by: Bressan, Marco, et al.
Published: (2026)

3SUM in Preprocessed Universes: Faster and Simpler
by: Kasliwal, Shashwat, et al.
Published: (2024)

Simpler and Faster Directed Low-Diameter Decompositions
by: Li, Jason
Published: (2025)

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
by: Garg, Sachin, et al.
Published: (2025)