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

DOI10.1007/B13632zbMATH Open1266.90117OpenAlexW1827234103MaRDI QIDQ5897232FDOQ5897232

Ranjithkumar Rajagopalan, Aaron Archer, 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)

Cited In (12)

• Incremental medians via online bidding
• Approximating \(k\)-median via pseudo-approximation
• Universal Algorithms for Clustering Problems
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Local search algorithms for the red-blue median problem
• LP-based approximation for uniform capacitated facility location problem
• Near-optimal clustering in the \(k\)-machine model
• Partial multicuts in trees
• Title not available (Why is that?)
• Analytical aspects of tie breaking
• Approximation algorithms for hard capacitated \(k\)-facility location problems

   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 👍 👎

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)