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

2015/02/24 by Ching-Lueh Chang, Chang, Ching-Lueh · 1 citation
Computer Science · Engineering · #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1502.06764

openalex publication_date 2015/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a deterministic O(hn^1+1/h)-time (2h)-approximation nonadaptive algorithm for 1-median selection in n-point metric spaces, where h∈ℤ⁺∖\1\ is arbitrary. Our proof generalizes that of Chang.

Cited by

• Metric 1-median selection: Query complexity vs. approximation ratio

Related

• A lower bound for metric 1-median selection
• A Las Vegas approximation algorithm for metric 1-median selection
• Deterministic metric 1-median selection with very few queries
• Metric 1-median selection: Query complexity vs. approximation ratio
• Metric 1-median selection with fewer queries