Cover Image

A near-linear time approximation scheme for $(k,\ell)$-median clustering under discrete Fréchet distance

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Driemel, Anne, Höckendorff, Jan, Psarros, Ioannis, Sohler, Christian
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

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
by: Driemel, Anne, et al.
Published: (2026)

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

A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs
by: Fox, Emily
Published: (2023)

Property Testing of Computational Networks
by: Czumaj, Artur, et al.
Published: (2025)

Faster Approximation Algorithms for k-Center via Data Reduction
by: Filtser, Arnold, et al.
Published: (2025)

On the adversarial robustness of Locality-Sensitive Hashing in Hamming space
by: Kapralov, Michael, et al.
Published: (2024)

Testing Depth First Search Numbering
by: Czumaj, Artur, et al.
Published: (2025)

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
by: Peng, Pan, et al.
Published: (2025)

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

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
by: Kumar, Mithilesh, et al.
Published: (2016)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
by: Makarychev, Konstantin, et al.
Published: (2025)

The anti-lexicographic SUS-anchor: a near-optimal k=1 sampling scheme
by: Koerkamp, Groot, et al.
Published: (2026)

On computing the (exact) Fréchet distance with a frog
by: Conradi, Jacobus, et al.
Published: (2025)

Quasilinear-time eccentricities computation, and more, on median graphs
by: Bergé, Pierre, et al.
Published: (2024)

Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem
by: Madani, Amirali, et al.
Published: (2025)

New approximate distance oracles and their applications
by: Kadria, Avi, et al.
Published: (2025)

Learning-Augmented Algorithms for $k$-median via Online Learning
by: Hebbar, Anish, et al.
Published: (2026)

Bicriteria approximation for $k$-edge-connectivity
by: Nutov, Zeev, et al.
Published: (2025)

Randomized $k$-server in polynomial time
by: Coester, Christian, et al.
Published: (2026)

Dynamic k-center clustering with lifetimes
by: Moretti, Simone, et al.
Published: (2026)

Improved bicriteria approximation for $k$-edge-connectivity
by: Nutov, Zeev
Published: (2025)

Beyond 2-approximation for k-Center in Graphs
by: Jin, Ce, et al.
Published: (2025)

Binary weights spanning trees and the $k$-red spanning tree problem in linear time
by: Hochbaum, Dorit S.
Published: (2024)

A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree
by: Elkin, Yury, et al.
Published: (2021)

Fast approximation algorithms for the 1-median problem on real-world large graphs
by: Ueta, Keisuke, et al.
Published: (2025)

An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths
by: Nutov, Zeev
Published: (2022)

Range Counting Oracles for Geometric Problems
by: Driemel, Anne, et al.
Published: (2025)

Dynamic Metric Embedding into $\ell_p$ Space
by: Banihashem, Kiarash, et al.
Published: (2024)

On Practical Nearest Sub-Trajectory Queries under the Fréchet Distance
by: Gudmundsson, Joachim, et al.
Published: (2022)

On estimating the quantum $\ell_α$ distance
by: Liu, Yupan, et al.
Published: (2025)

$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
by: Fischer, Nick, et al.
Published: (2025)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
by: Makarychev, Yury, et al.
Published: (2024)

Fast approximate $\ell$-center clustering in high dimensional spaces
by: Kowaluk, Mirosław, et al.
Published: (2025)

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

Improved fixed-parameter bounds for Min-Sum-Radii and Diameters $k$-clustering and their fair variants
by: Banerjee, Sandip, et al.
Published: (2025)

Fitting trees to $\ell_1$-hyperbolic distances
by: Yim, Joon-Hyeok, et al.
Published: (2024)

Smallest suffixient set maintenance in near-real-time
by: Köppl, Dominik, et al.
Published: (2026)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
by: Armbruster, Alexander, et al.
Published: (2025)

On Finding $\ell$-th Smallest Perfect Matchings
by: Maalouly, Nicolas El, et al.
Published: (2025)

Approximations for Fault-Tolerant Total and Partial Positive Influence Domination
by: Lamprou, Ioannis, et al.
Published: (2025)