Cover Image

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Driemel, Anne, Höckendorff, Jan, Psarros, Ioannis, Sohler, Christian, Yue, Di
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A near-linear time approximation scheme for $(k,\ell)$-median clustering under discrete Fréchet distance
by: Driemel, Anne, et al.
Published: (2025)

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

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
by: Ren, Kinter, et al.
Published: (2024)

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

Approximating Partition in Near-Linear Time
by: Chen, Lin, et al.
Published: (2024)

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

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

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

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
by: Henzinger, Monika, et al.
Published: (2025)

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
by: Buchem, Moritz, et al.
Published: (2024)

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)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Mömke, Tobias, et al.
Published: (2024)

Clustering under Constraints: Efficient Parameterized Approximation Schemes
by: Bhore, Sujoy, et al.
Published: (2025)

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
by: Harada, Kaito, et al.
Published: (2024)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
by: Henzinger, Monika, et al.
Published: (2024)

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

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

Parameterized Linear Time Transitive Closure
by: Kritikakis, Giorgos, et al.
Published: (2024)

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
by: Agarwal, Arpit, et al.
Published: (2024)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
by: Mao, Xiao
Published: (2023)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

Improved Tree Sparsifiers in Near-Linear Time
by: Agassy, Daniel, et al.
Published: (2025)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
by: Mao, Xiao, et al.
Published: (2026)

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

Deterministic $k$-Median Clustering in Near-Optimal Time
by: Costa, Martín, et al.
Published: (2025)

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

Clustering in Varying Metrics
by: Chakrabarty, Deeparnab, et al.
Published: (2025)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

Deterministic Longest Common Subsequence Approximation in Near-Linear Time
by: Boneh, Itai, et al.
Published: (2025)

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
by: Nezhad, Sina Bagheri, et al.
Published: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

Learning to Approximate Uniform Facility Location via Graph Neural Networks
by: Qian, Chendi, et al.
Published: (2026)

Approximating $q \rightarrow p$ Norms of Non-Negative Matrices in Nearly-Linear Time
by: Objois, Étienne, et al.
Published: (2025)

Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
by: Terao, Tatsuya
Published: (2024)

Additive Approximation Schemes for Low-Dimensional Embeddings
by: Anderson, Prashanti, et al.
Published: (2025)

Approximation Schemes for Planar Graph Connectivity Problems
by: Neuwohner, Meike, et al.
Published: (2025)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
by: Elkin, Michael, et al.
Published: (2024)