arXiv Open Access 2015

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

Ching-Lueh Chang

Lihat Sumber

Abstrak

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-Ω(1))$-approximation algorithms for any constant $h\in\mathbb{Z}^+\setminus\{1\}$.

Topik & Kata Kunci

cs.CC

Penulis (1)

Ching-Lueh Chang

Format Sitasi

APA MLA BibTeX

Chang, C. (2015). Metric $1$-median selection: Query complexity vs. approximation ratio. https://arxiv.org/abs/1509.05662

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2015
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓