The reverse greedy algorithm for the metric k-median problem

DOI10.1016/J.IPL.2005.09.009MaRDI QIDQ1045901zbMATH OpenOpenAlexFDO

Authors Marek Chrobak, Claire Kenyon, Neal E. Young

Publication date 18 December 2009

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationonline algorithmsanalysis of algorithmsapproximation algorithmsfacility location

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25)

Abstract: The Reverse Greedy algorithm (RGreedy) for the k-median problem works as follows. It starts by placing facilities on all nodes. At each step, it removes a facility to minimize the resulting total distance from the customers to the remaining facilities. It stops when k facilities remain. We prove that, if the distance function is metric, then the approximation ratio of RGreedy is between ?(log n/ log log n) and O(log n).

Recommendations

• Computing and Combinatorics
• A constant-factor approximation algorithm for the k-median problem
• A new approximation algorithm for the \(k\)-facility location problem
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• The Online Median Problem

Cites work

• scientific article; zbMATH DE number 1559578 (Why is no real title available?)
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• A new greedy approach for facility location problems
• Approximation algorithms for hierarchical location problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Incremental Clustering and Dynamic Information Retrieval
• Local search heuristic for k-median and facility location problems
• The Online Median Problem

Cited in

(3)

• Incremental medians via online bidding
• Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid
• Computing and Combinatorics

This page was built for publication: The reverse greedy algorithm for the metric k-median problem

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