Approximation Algorithms for the k-Median Problem

DOI10.1007/11671541_10MaRDI QIDQ5450811zbMATH OpenOpenAlexFDO

Authors Roberto Solis-Oba

Publication date 14 March 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11671541_10

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Approximation algorithms (68W25)

Recommendations

• A constant-factor approximation algorithm for the k-median problem
• An improved approximation algorithm for the hard uniform capacitated k-median problem
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• A bicriteria approximation algorithm for the \(k\)-center and \(k\)-median problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation

Cited in

(15)

• Approximating k-median via pseudo-approximation
• Online facility location with facility movements
• scientific article; zbMATH DE number 2165699 (Why is no real title available?)
• Approximating k-median via pseudo-approximation
• An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• An approximation algorithm for the \(k\)-median warehouse-retailer network design problem
• A bicriteria approximation algorithm for the \(k\)-center and \(k\)-median problems
• scientific article; zbMATH DE number 7561535 (Why is no real title available?)
• An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
• An approximation algorithm for the \(p\)-hub median problem
• A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median
• Efficient Algorithms for the Capacitated 1-Median Problem
• scientific article; zbMATH DE number 1416475 (Why is no real title available?)
• Better guarantees for \(k\)-median with service installation costs

This page was built for publication: Approximation Algorithms for the k-Median Problem

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