On Las Vegas approximations for metric 1-median selection

DOI10.1016/j.ipl.2019.02.007zbMath1478.68447OpenAlexW2918722366WikidataQ128310397 ScholiaQ128310397MaRDI QIDQ1739219

Ching-Lueh Chang

Publication date: 26 April 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2019.02.007

zbMATH Keywords

metric space1-mediansublinear-time algorithmcloseness centralityrandomized aigorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Metric spaces, metrizability (54E35) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

On random perfect matchings in metric spaces with not-too-large diameters

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal time bounds for approximate clustering
• Deterministic sublinear-time approximations for metric 1-median selection
• On approximating metric 1-median in sublinear time
• Sublinear time algorithms for metric space problems
• Approximating average parameters of graphs
• Linear-time approximation schemes for clustering problems in any dimensions
• On Approximating the Average Distance Between Points
• Fast Approximation of Centrality
• Metric 1-Median Selection