Streaming Euclidean MST to a Constant Factor.

Xi Chen Vincent Cohen-Addad Rajesh Jayaram Amit Levi Erik Waingarten

Published in: STOC (2023)

Keyphrases

constant factor
approximation algorithms
lower bound
worst case
upper bound
minimal spanning tree
data streams
minimum spanning tree
euclidean space
sample complexity
special case
small number
primal dual
convex hull
data sets
multi class
computational complexity
objective function
decision trees