The reverse greedy algorithm for the metric k-median problem

DOI10.1016/j.ipl.2005.09.009zbMath1184.68631arXivcs/0504104OpenAlexW2161747341MaRDI QIDQ1045901

Marek Chrobak, Neal E. Young, Claire M. Kenyon

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 algorithmsfacility locationapproximation algorithms

Mathematics Subject Classification ID

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

Related Items (2)

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

Cites Work

• Unnamed Item
• 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
• Incremental Clustering and Dynamic Information Retrieval
• The Online Median Problem
• Local search heuristic for k-median and facility location problems
• Approximation algorithms for hierarchical location problems

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