Metric 1-median selection: query complexity vs. approximation ratio

DOI10.1007/978-3-319-42634-1_11MaRDI QIDQ2817856zbMATH OpenOpenAlexFDO

Authors Ching-Lueh Chang

Publication date 2 September 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: Consider the problem of finding a point in a metric space $(1,2,ldots,n,d)$ with the minimum average distance to other points. We show that this problem has no deterministic $o(n^{1+1/(h-1)})$-query $(2h-Omega(1))$-approximation algorithms for any constant $hinmathbb{Z}^{+}setminus1$.

Recommendations

• Metric 1-median selection: query complexity vs. approximation ratio
• A lower bound for metric 1-median selection
• Some results on approximate 1-median selection in metric spaces
• Deterministic sublinear-time approximations for metric 1-median selection
• On Las Vegas approximations for metric 1-median selection

Cites work

• A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection
• A simple \(D ^{2}\)-sampling based PTAS for \(k\)-means and other clustering problems
• Deterministic sublinear-time approximations for metric 1-median selection
• Linear-time approximation schemes for clustering problems in any dimensions
• Local Search Heuristics for k-Median and Facility Location Problems
• On approximating metric 1-median in sublinear time
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• Optimal time bounds for approximate clustering
• Some results on approximate 1-median selection in metric spaces
• Sublinear time algorithms for metric space problems

Cited in

(5)

• On Las Vegas approximations for metric 1-median selection
• On ultrametric 1-median selection
• A lower bound for metric 1-median selection
• Some results on approximate 1-median selection in metric spaces
• Metric 1-median selection: query complexity vs. approximation ratio

This page was built for publication: Metric 1-median selection: query complexity vs. approximation ratio

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