Buchumschlag

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Cohen-Addad, Vincent, d'Orsi, Tommaso, Mousavifar, Aida
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Machine Learning F.2; G.3
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Multi-View Stochastic Block Models
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

Perturb-and-Project: Differentially Private Similarities and Marginals
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

Max-Cut with $ε$-Accurate Predictions
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
von: Anand, Aditya, et al.
Veröffentlicht: (2025)

On Purely Private Covariance Estimation
von: d'Orsi, Tommaso, et al.
Veröffentlicht: (2025)

Tight Differentially Private PCA via Matrix Coherence
von: d'Orsi, Tommaso, et al.
Veröffentlicht: (2025)

Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
von: Spielman, Daniel A., et al.
Veröffentlicht: (2006)

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

Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2023)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
von: Bansal, Nikhil, et al.
Veröffentlicht: (2024)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

Near-Linear Time Computation of Welzl Orders on Graphs with Linear Neighborhood Complexity
von: Dreier, Jan, et al.
Veröffentlicht: (2026)

Distributed Algorithms for Euclidean Clustering
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
von: Kapralov, Michael, et al.
Veröffentlicht: (2022)

Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors
von: Kao, Ming-Yang, et al.
Veröffentlicht: (1999)

Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence
von: AmaniHamedani, Alireza, et al.
Veröffentlicht: (2024)

Combinatorial Optimization using Comparison Oracles
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
von: Farfan, Angelo, et al.
Veröffentlicht: (2025)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

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

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

Deterministic Longest Common Subsequence Approximation in Near-Linear Time
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Beyond Worst Case Local Computation Algorithms
von: Biswas, Amartya Shankha, et al.
Veröffentlicht: (2024)

A Linear-Time 1.5-Approximation for Broadcasting in k-Cycle Graphs
von: Bringolf, Jeffrey, et al.
Veröffentlicht: (2025)

Dynamic Correlation Clustering in Sublinear Update Time
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

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

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
von: d'Orsi, Tommaso, et al.
Veröffentlicht: (2024)

Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$
von: Spielman, Daniel A., et al.
Veröffentlicht: (2003)

A Simple yet Exact Analysis of the MultiQueue
von: Walzer, Stefan, et al.
Veröffentlicht: (2024)

Towards a Parameterized Approximation Dichotomy of MinCSP for Linear Equations over Finite Commutative Rings
von: Dabrowski, Konrad K., et al.
Veröffentlicht: (2024)

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

Approximation Algorithms for Action-Reward Query-Commit Matching
von: Derakhshan, Mahsa, et al.
Veröffentlicht: (2026)

Fixed-parameter tractable inference for discrete probabilistic programs, via string diagram algebraisation
von: Peterseim, Benedikt, et al.
Veröffentlicht: (2026)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
von: Driemel, Anne, et al.
Veröffentlicht: (2026)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
von: Grilnberger, Mara, et al.
Veröffentlicht: (2026)

Fair Clustering in the Sliding Window Model
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

Combinatorial Correlation Clustering
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

Simpler and Unified Recognition Algorithm for Path Graphs and Directed Path Graphs
von: Balzotti, Lorenzo
Veröffentlicht: (2020)

Connected Components in Linear Work and Near-Optimal Time
von: Farhadi, Alireza, et al.
Veröffentlicht: (2023)