A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection

DOI10.1016/J.TCS.2015.07.058MaRDI QIDQ497691zbMATH OpenOpenAlexFDO

Authors Ching-Lueh Chang

Publication date 25 September 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.06764

zbMATH Keywords

\(k\)-median selection1-median selectioncloseness centralitymetric spacesublinear-time algorithm

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Abstract: We give a deterministic $O(h{n}^{1+1/h})$-time $(2h)$-approximation nonadaptive algorithm for $1$-median selection in $n$-point metric spaces, where $hinmathbb{Z}^{+}setminus1$ is arbitrary. Our proof generalizes that of Chang.

Recommendations

• Deterministic sublinear-time approximations for metric 1-median selection
• Some results on approximate 1-median selection in metric spaces
• A lower bound for metric 1-median selection
• On approximating metric 1-median in sublinear time
• An Efficient Approximate Algorithm for the 1-Median Problem in Metric Spaces

Cites work

• Clustering for metric and nonmetric distance measures
• Deterministic sublinear-time approximations for metric 1-median selection
• Linear-time approximation schemes for clustering problems in any dimensions
• On approximating metric 1-median in sublinear time
• Sublinear time algorithms for metric space problems

Cited in

(6)

• Deterministic sublinear-time approximations for metric 1-median selection
• On approximating metric 1-median in sublinear time
• Metric 1-median selection: query complexity vs. approximation ratio
• A lower bound for metric 1-median selection
• An Efficient Approximate Algorithm for the 1-Median Problem in Metric Spaces
• Experimental and Efficient Algorithms

This page was built for publication: A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q497691)