Sublinear time approximation of the cost of a metric \(k\)-nearest neighbor graph

DOI10.1137/22M1544105MaRDI QIDQ6491305

Christian Sohler, Artur Czumaj

Publication date: 24 April 2024

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmnearest neighborssublinear algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal time bounds for approximate clustering
• Binomial approximation to the Poisson binomial distribution
• Sublinear time algorithms for metric space problems
• Approximating average parameters of graphs
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data
• An improved constant-time approximation algorithm for maximum~matchings
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Locality-sensitive hashing scheme based on p-stable distributions
• Testing Closeness of Discrete Distributions
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• Automata, Languages and Programming

This page was built for publication: Sublinear time approximation of the cost of a metric \(k\)-nearest neighbor graph