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

DOI10.1007/978-3-642-31594-7_17zbMATH Open1272.90020OpenAlexW169553655MaRDI QIDQ2843247FDOQ2843247

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) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Cited In (27)

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

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

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