Imagen de Portada

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

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Greenhut, Daniel, Feldman, Dan
Formato:	Preprint
Publicado:	2025
Materias:	Machine Learning Computational Geometry Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

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

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

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

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

Terminal Embeddings in Sublinear Time
por: Cherapanamjeri, Yeshwanth, et al.
Publicado: (2021)

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

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

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

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

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

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

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

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

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

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

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

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

Space Complexity of Euclidean Clustering
por: Zhu, Xiaoyi, et al.
Publicado: (2024)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Parameterized Approximation of Rectangle Stabbing
por: Chu, Huairui, et al.
Publicado: (2026)

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

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

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