On Uniform Capacitated k -Median Beyond the Natural LP Relaxation

DOI10.1145/2983633zbMath1451.90089OpenAlexW3162123198MaRDI QIDQ4962655

Shi Li

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2983633

zbMATH Keywords

approximation algorithmscapacitated \(k\)-medianpseudoapproximation

Mathematics Subject Classification ID

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

Related Items

A Technique for Obtaining True Approximations for k-Center with Covering Constraints ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ Improved parameterized approximation for balanced \(k\)-median ⋮ Approximation algorithms for two variants of correlation clustering problem ⋮ On colorful vertex and edge cover problems ⋮ Improved bounds for metric capacitated covering problems ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Tight FPT approximation for socially fair clustering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A constant FPT approximation algorithm for hard-capacitated \(k\)-means ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ On the cost of essentially fair clusterings ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ Faster balanced clusterings in high dimension ⋮ Lossy kernelization of same-size clustering ⋮ Unnamed Item ⋮ Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs ⋮ Constant Approximation Algorithm for Nonuniform Capacitated Multi-Item Lot Sizing via Strong Covering Inequalities ⋮ Lossy kernelization of same-size clustering ⋮ On parameterized approximation algorithms for balanced clustering ⋮ A technique for obtaining true approximations for \(k\)-center with covering constraints