Deterministic metric 1-median selection with A \(1-o(1)\) fraction of points ignored

DOI10.1007/978-3-030-89543-3_18OpenAlexW3209595692MaRDI QIDQ2695287

Ching-Lueh Chang

Publication date: 30 March 2023

Full work available at URL: https://doi.org/10.1007/978-3-030-89543-3_18

zbMATH Keywords

metric spacequery complexity1-median problemsublinear algorithmmedian selection

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• A lower bound for metric 1-median selection
• Fast approximations for sums of distances, clustering and the Fermat-Weber problem
• 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
• A new greedy approach for facility location problems
• Fast Approximation of Centrality
• Metric 1-Median Selection
• Unnamed Item
• Unnamed Item

This page was built for publication: Deterministic metric 1-median selection with A \(1-o(1)\) fraction of points ignored