Lagrangian relaxation for the k-median problem: new insights and continuity properties

DOI10.1007/B13632MaRDI QIDQ5897232zbMATHOpenAlexFDO

Authors Aaron Archer, Ranjithkumar Rajagopalan, David B. Shmoys

Publication date 3 March 2010

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

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

Mathematics Subject Classification ID

Approximation algorithms (68W25) Integer programming (90C10) Discrete location and assignment (90B80)

Recommendations

• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A dependent LP-rounding approach for the \(k\)-median problem
• A new approximation algorithm for the \(k\)-facility location problem
• Theory and Applications of Models of Computation
• Local Search Heuristics for k-Median and Facility Location Problems

Cited in

(12)

• Universal Algorithms for Clustering Problems
• Near-optimal clustering in the \(k\)-machine model
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Incremental medians via online bidding
• Approximating \(k\)-median via pseudo-approximation
• Partial multicuts in trees
• Large-scale distributed algorithms for facility location with outliers
• Local search algorithms for the red-blue median problem
• LP-based approximation for uniform capacitated facility location problem
• Analytical aspects of tie breaking
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Approximation algorithms for hard capacitated \(k\)-facility location problems

This page was built for publication: Lagrangian relaxation for the \(k\)-median problem: new insights and continuity properties

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