Constant Factor Approximation for Capacitated k-Center with Outliers

DOI10.4230/LIPIcs.STACS.2014.251zbMath1359.90056arXiv1401.2874OpenAlexW2963591265MaRDI QIDQ2965488

Marek Cygan, Tomasz Kociumaka

Publication date: 3 March 2017

Full work available at URL: https://arxiv.org/abs/1401.2874

zbMATH Keywords

outliersapproximation algorithms\(k\)-centercapacitiesLP rounding

Mathematics Subject Classification ID

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

Related Items (7)

Generalized \(k\)-center: distinguishing doubling and highway dimension ⋮ Unnamed Item ⋮ Capacitated facility location with outliers/penalties ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ On the cost of essentially fair clusterings ⋮ Improved approximation algorithms for capacitated fault-tolerant \(k\)-center ⋮ Faster balanced clusterings in high dimension

This page was built for publication: Constant Factor Approximation for Capacitated k-Center with Outliers