Geometric Approximation Algorithms

415 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Protocols for Learning Classifiers on Distributed Data (2012, background): “sy setting. Most of the results presented in this paper generalize to noisy data. In fact, Theorem 2.1 and Theorem 3.1 have straight-forward extensions to the noisy case by an "-sample argument (Har-peled, 2011). This would increase the communication from O(1=") to about O(1="2). It w”
Practical Coreset Constructions for Machine Learning (2017, background): “However, this bound corresponds to a generalization of the primal shattering dimension in classical VC theory to continuous loss functions [Har-Peled, 2011, Matousek, 2009], and is hence not the one required by Li et al. [2001].”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, methodology): “For any point-set P of size n and query set Q of size n O (1) the algorithm is adaptive with respect to P and Q , with the failure probability of at most 1 /n .”