A Dependent LP-Rounding Approach for the k-Median Problem

DOI10.1007/978-3-642-31594-7_17zbMath1272.90020OpenAlexW169553655MaRDI QIDQ2843247

Shi Li, Moses Charikar

Publication date: 12 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-31594-7_17

zbMATH Keywords

approximationdependent rounding\(k\)-median problem

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items

An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties ⋮ Provable randomized rounding for minimum-similarity diversification ⋮ Matroid and knapsack center problems ⋮ An Improved Approximation Algorithm for Knapsack Median Using Sparsification ⋮ An improved approximation algorithm for squared metric \(k\)-facility location ⋮ Improved parameterized approximation for balanced \(k\)-median ⋮ Unnamed Item ⋮ Constant approximation for fault-tolerant median problems via iterative rounding ⋮ An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee ⋮ Approximation algorithms for clustering with dynamic points ⋮ LP-based approximation for uniform capacitated facility location problem ⋮ The distance-constrained matroid median problem ⋮ On clustering with discounts ⋮ Approximation Algorithms for Matroid and Knapsack Means Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation schemes for \(k\)-facility location ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ An improved approximation algorithm for knapsack median using sparsification ⋮ Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems ⋮ Approximating $k$-Median via Pseudo-Approximation ⋮ Improved approximation for prize-collecting red-blue median ⋮ Constant factor approximation algorithm for uniform hard capacitated knapsack median problem ⋮ Facility Location with Matroid or Knapsack Constraints ⋮ Improved approximation algorithms for solving the squared metric \(k\)-facility location problem ⋮ Scenario reduction revisited: fundamental limits and guarantees

This page was built for publication: A Dependent LP-Rounding Approach for the k-Median Problem