Local Search for Clustering in Almost-linear Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jiang, Shaofeng H. -C., Jin, Yaonan, Lou, Jianing, Lu, Pinyan
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Round-efficient Fully-scalable MPC algorithms for k-Means
by: Jiang, Shaofeng H. -C., et al.
Published: (2026)

Coresets for Robust Clustering via Black-box Reductions to Vanilla Case
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Fully Dynamic Euclidean k-Means
by: Bhattacharya, Sayan, et al.
Published: (2025)

Coresets for Kernel Clustering
by: Jiang, Shaofeng H. -C., et al.
Published: (2021)

Moderate Dimension Reduction for $k$-Center Clustering
by: Jiang, Shaofeng H. -C., et al.
Published: (2023)

Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds
by: Huang, Lingxiao, et al.
Published: (2023)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Fair Clustering in the Sliding Window Model
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Relative Error Fair Clustering in the Weak-Strong Oracle Model
by: Braverman, Vladimir, et al.
Published: (2025)

Streaming Max-Cut in General Metrics
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Local Search-based Individually Fair Clustering with Outliers
by: Maity, Binita, et al.
Published: (2025)

Network Unreliability in Almost-Linear Time
by: Cen, Ruoxu, et al.
Published: (2025)

Deterministic Mincut in Almost-Linear Time
by: Li, Jason
Published: (2021)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Near-Optimal Dimension Reduction for Facility Location
by: Huang, Lingxiao, et al.
Published: (2024)

Streaming Algorithms for Geometric Steiner Forest
by: Czumaj, Artur, et al.
Published: (2020)

Sample-Based Matroid Prophet Inequalities
by: Fu, Hu, et al.
Published: (2024)

Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
by: Goyal, Dishant, et al.
Published: (2024)

Approximating Directed Connectivity in Almost-Linear Time
by: Quanrud, Kent
Published: (2025)

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, et al.
Published: (2025)

Deterministic Almost-Linear-Time Gomory-Hu Trees
by: Abboud, Amir, et al.
Published: (2025)

Bellman-Ford in Almost-Linear Time for Dense Graphs
by: Li, George Z., et al.
Published: (2026)

Approximating Maximum Matching Requires Almost Quadratic Time
by: Behnezhad, Soheil, et al.
Published: (2024)

Solving Hypergraph Laplacian Systems in Almost-Linear Time
by: Yoshida, Yuichi
Published: (2026)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
by: Adar, Tomer, et al.
Published: (2026)

Hierarchical Clustering via Local Search
by: Jowhari, Hossein
Published: (2024)

Tree Embedding in High Dimensions: Dynamic and Massively Parallel
by: Goranci, Gramoz, et al.
Published: (2025)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
by: Jiang, Shunhua, et al.
Published: (2025)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
by: Bucić, Matija, et al.
Published: (2025)

Almost-Optimal Local-Search Methods for Sparse Tensor PCA
by: Lovig, Max, et al.
Published: (2025)

Fully Dynamic Algorithms for Chamfer Distance
by: Goranci, Gramoz, et al.
Published: (2025)

Fully Scalable MPC Algorithms for Clustering in High Dimension
by: Czumaj, Artur, et al.
Published: (2023)

Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method
by: Liu, Yang P.
Published: (2025)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
by: Brand, Jan van den, et al.
Published: (2024)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
by: Blikstad, Joakim, et al.
Published: (2025)

Almost succinct representation of maximal palindromes
by: Mieno, Takuya, et al.
Published: (2025)

Expander Decomposition with Almost Optimal Overhead
by: Bansal, Nikhil, et al.
Published: (2026)

Almost-Optimal Sublinear Additive Spanners
by: Tan, Zihan, et al.
Published: (2023)

Distances in Planar Graphs are Almost for Free!
by: Mozes, Shay, et al.
Published: (2026)