The reverse greedy algorithm for the metric k-median problem

DOI10.1016/J.IPL.2005.09.009zbMATH Open1184.68631arXivcs/0504104OpenAlexW2161747341MaRDI QIDQ1045901FDOQ1045901

Authors: Marek Chrobak, Claire Kenyon, Neal E. Young 

Publication date: 18 December 2009

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

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).

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

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

zbMATH Keywords

combinatorial optimizationonline algorithmsanalysis of algorithmsapproximation algorithmsfacility location

Mathematics Subject Classification ID

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

Cites Work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A new greedy approach for facility location problems
• The Online Median Problem
• Local search heuristic for k-median and facility location problems
• Incremental Clustering and Dynamic Information Retrieval
• Title not available (Why is that?)
• Approximation algorithms for hierarchical location problems

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)