Cover Image

Space Complexity of Euclidean Clustering

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zhu, Xiaoyi, Tian, Yuxiang, Huang, Lingxiao, Huang, Zengfeng
Format:	Preprint
Published:	2024
Subjects:	Computational Geometry Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
by: Huang, Lingxiao, et al.
Published: (2022)

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

Sublinear Spectral Clustering Oracle with Little Memory
by: Shen, Ranran, et al.
Published: (2026)

On Tight Robust Coresets for $k$-Medians Clustering
by: Huang, Lingxiao, et al.
Published: (2025)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Coresets for Clustering Under Stochastic Noise
by: Huang, Lingxiao, et al.
Published: (2025)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers
by: Fang, Ziyi, et al.
Published: (2025)

Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
by: Huang, Zengfeng, et al.
Published: (2025)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

Euclidean distance compression via deep random features
by: Leroux, Brett, et al.
Published: (2024)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
by: Bartlmae, Simon, et al.
Published: (2024)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
by: Bandyapadhyay, Sayan, et al.
Published: (2023)

Clustered Planarity Variants for Level Graphs
by: Fink, Simon D., et al.
Published: (2024)

Efficient Greedy Discrete Subtrajectory Clustering
by: van der Hoog, Ivor, et al.
Published: (2025)

On connections between k-coloring and Euclidean k-means
by: Aman, Enver, et al.
Published: (2024)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Exact Algorithms for Clustered Planarity with Linear Saturators
by: Da Lozzo, Giordano, et al.
Published: (2024)

The Complexity of Geodesic Spanners
by: de Berg, Sarita, et al.
Published: (2023)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Kisfaludi-Bak, Sándor, et al.
Published: (2020)

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
by: Gadekar, Ameet, et al.
Published: (2025)

Fréchet Distance in Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2024)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
by: Abbasi, Fateme, et al.
Published: (2023)

Hybrid k-Clustering: Blending k-Median and k-Center
by: Fomin, Fedor V., et al.
Published: (2024)

The Parameterized Complexity of Extending Stack Layouts
by: Depian, Thomas, et al.
Published: (2024)

Polyline Simplification has Cubic Complexity
by: Bringmann, Karl, et al.
Published: (2018)

The Complexity of Geodesic Spanners using Steiner Points
by: de Berg, Sarita, et al.
Published: (2024)

On the Complexity of the Ordered Covering Problem in Distance Geometry
by: Souza, Michael, et al.
Published: (2025)

Optimal Trajectories in Discrete Space with Acceleration Constraints
by: Casteigts, Arnaud, et al.
Published: (2026)

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
by: Maus, Victor, et al.
Published: (2026)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
by: Grandoni, Fabrizio, et al.
Published: (2026)

Shortest Path Separators in Unit Disk Graphs
by: Harb, Elfarouk, et al.
Published: (2024)

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2025)

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
by: Banik, Aritra, et al.
Published: (2024)

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

An Algorithm for Fast and Correct Computation of Reeb Spaces for PL Bivariate Fields
by: Chattopadhyay, Amit, et al.
Published: (2024)

Spanner for the $0/1/\infty$ weighted region problem
by: Gudmundsson, Joachim, et al.
Published: (2024)

Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality
by: Fomin, Fedor V., et al.
Published: (2026)

Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
by: de Berg, Sarita, et al.
Published: (2023)