Cover Image

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Greenhut, Daniel, Feldman, Dan
Format:	Preprint
Published:	2025
Subjects:	Machine Learning 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

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

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

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

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

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
by: Krivošija, Amer, et al.
Published: (2025)

Approximating Fair $k$-Min-Sum-Radii in Euclidean Space
by: Drexler, Lukas, et al.
Published: (2023)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
by: Ebbens, Matthijs, et al.
Published: (2024)

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

Terminal Embeddings in Sublinear Time
by: Cherapanamjeri, Yeshwanth, et al.
Published: (2021)

Data Structures for Approximate Discrete Fréchet Distance
by: van der Hoog, Ivor, et al.
Published: (2022)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
by: S, Ajaykrishnan E, et al.
Published: (2025)

Approximate Algorithms for Chamfer Distance Under Translation
by: Halevi, Gil, et al.
Published: (2026)

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

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

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
by: Bentert, Matthias, et al.
Published: (2025)

On Approximability of $\ell_2^2$ Min-Sum Clustering
by: S., Karthik C., et al.
Published: (2024)

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

2-Layer Fan-Planarity in Polynomial Time
by: Kobayashi, Yasuaki, et al.
Published: (2025)

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

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

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
by: Galby, Esther, et al.
Published: (2023)

Space Complexity of Euclidean Clustering
by: Zhu, Xiaoyi, et al.
Published: (2024)

Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time
by: Eppstein, David
Published: (2023)

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

TimeCluster with PCA is Equivalent to Subspace Identification of Linear Dynamical Systems
by: Hines, Christian L., et al.
Published: (2025)

Fast Agnostic Learners in the Plane
by: Eden, Talya, et al.
Published: (2025)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
by: Cohen-Addad, Vincent, et al.
Published: (2025)

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

A Query-Driven Approach to Space-Efficient Range Searching
by: Fotakis, Dimitris, et al.
Published: (2025)

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

Graph-Based Nearest-Neighbor Search without the Spread
by: Giliberti, Jeff, et al.
Published: (2026)

Hardness of High-Dimensional Linear Classification
by: Munteanu, Alexander, et al.
Published: (2026)

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

Sequential non-determinism in tile self-assembly: a general framework and an application to efficient temperature-1 self-assembly of squares
by: Furcy, David, et al.
Published: (2024)

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

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

Parameterized Approximation of Rectangle Stabbing
by: Chu, Huairui, et al.
Published: (2026)

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
by: Funk, Nicole, et al.
Published: (2026)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
by: Bandyapadhyay, Sayan, et al.
Published: (2024)