An Efficient Approximate Algorithm for the 1-Median Problem in Metric Spaces

DOI10.1137/S1052623403424740zbMath1094.68117OpenAlexW1985786140MaRDI QIDQ5470203

Alfredo Pulvirenti, Domenico Cantone, Alfredo Ferro, Gianluca Cincotti

Publication date: 30 May 2006

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s1052623403424740

zbMATH Keywords

approximation algorithmsrandomized algorithmsFermat-Weber problemselection algorithms1-median problemalgorithms for metric spacesclustroid selection

Mathematics Subject Classification ID

Metric spaces, metrizability (54E35) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Randomized algorithms (68W20) General biology and biomathematics (92B05)

Related Items (2)

On approximating metric 1-median in sublinear time ⋮ An efficient noisy binary search in graphs via Median approximation

This page was built for publication: An Efficient Approximate Algorithm for the 1-Median Problem in Metric Spaces