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

DOI10.1137/S1052623403424740MaRDI QIDQ5470203zbMATH OpenOpenAlexFDO

Authors Domenico Cantone, Alfredo Ferro, Alfredo Pulvirenti, 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

1-median problemalgorithms for metric spacesapproximation algorithmsclustroid selectionFermat-Weber problemrandomized algorithmsselection algorithms

Mathematics Subject Classification ID

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

Recommendations

• Some results on approximate 1-median selection in metric spaces
• On Las Vegas approximations for metric 1-median selection
• Deterministic sublinear-time approximations for metric 1-median selection
• An approximate median search algorithm in non-metric spaces
• A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection

Cited in

(13)

• On Las Vegas approximations for metric 1-median selection
• An efficient noisy binary search in graphs via Median approximation
• A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric
• On approximating metric 1-median in sublinear time
• Efficient algorithms for the round-trip 1-center and 1-median problems
• An approximate median search algorithm in non-metric spaces
• Finding the Median (Obliviously) with Bounded Space
• Efficient Algorithms for the Capacitated 1-Median Problem
• Some results on approximate 1-median selection in metric spaces
• scientific article; zbMATH DE number 2090207 (Why is no real title available?)
• A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection
• Experimental and Efficient Algorithms
• Algorithms with mediant convergents and their metrical theory

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

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