Geometric median in nearly linear time
From MaRDI portal
Publication:5361815
DOI10.1145/2897518.2897647zbMath1377.68267arXiv1606.05225OpenAlexW2410099853MaRDI QIDQ5361815
Aaron Sidford, Michael B. Cohen, Yin Tat Lee, Jakub W. Pachocki, Gary Lee Miller
Publication date: 29 September 2017
Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1606.05225
Analysis of algorithms and problem complexity (68Q25) Interior-point methods (90C51) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (15)
Medians in median graphs and their cube complexes in linear time ⋮ A causal filter of gradient information for enhanced robustness and resilience in distributed convex optimization ⋮ An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions ⋮ Mean estimation with sub-Gaussian rates in polynomial time ⋮ Mean estimation in high dimension ⋮ Hardness Results for Structured Linear Systems ⋮ Computing kemeny rankings from \(d\)-Euclidean preferences ⋮ Sub-Gaussian estimators of the mean of a random vector ⋮ Robust Estimators in High-Dimensions Without the Computational Intractability ⋮ Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering ⋮ On Geometric Prototype and Applications ⋮ Active-learning a convex body in low dimensions ⋮ Probabilistic smallest enclosing ball in high dimensions via subgradient sampling ⋮ Mean estimation and regression under heavy-tailed distributions: A survey ⋮ Approximation and complexity of the capacitated geometric median problem
This page was built for publication: Geometric median in nearly linear time
