Constant Factor Approximation for Capacitated k-Center with Outliers

DOI10.4230/LIPICS.STACS.2014.251zbMATH Open1359.90056arXiv1401.2874OpenAlexW2963591265MaRDI QIDQ2965488FDOQ2965488

Marek Cygan, Tomasz Kociumaka

Publication date: 3 March 2017

Abstract: The $k$-center problem is a classic facility location problem, where given an edge-weighted graph $G=(V,E)$ one is to find a subset of $k$ vertices $S$, such that each vertex in $V$ is "close" to some vertex in $S$. The approximation status of this basic problem is well understood, as a simple 2-approximation algorithm is known to be tight. Consequently different extensions were studied. In the capacitated version of the problem each vertex is assigned a capacity, which is a strict upper bound on the number of clients a facility can serve, when located at this vertex. A constant factor approximation for the capacitated $k$-center was obtained last year by Cygan, Hajiaghayi and Khuller [FOCS'12], which was recently improved to a 9-approximation by An, Bhaskara and Svensson [arXiv'13]. In a different generalization of the problem some clients (denoted as outliers) may be disregarded. Here we are additionally given an integer $p$ and the goal is to serve exactly $p$ clients, which the algorithm is free to choose. In 2001 Charikar et al. [SODA'01] presented a 3-approximation for the $k$-center problem with outliers. In this paper we consider a common generalization of the two extensions previously studied separately, i.e. we work with the capacitated $k$-center with outliers. We present the first constant factor approximation algorithm with approximation ratio of 25 even for the case of non-uniform hard capacities.

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

Recommendations

• Capacitated center problems with two-sided bounds and outliers
• An approximation algorithm for the \(k\)-level facility location problem with outliers
• Approximation algorithms for the individually fair \(k\)-center with outliers
• Exact algorithms for handling outliers in center location problems on networks using \(k\)-max functions
• Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center
• The capacitated \(K\)-center problem (extended abstract)
• Constant-Factor FPT Approximation for Capacitated k-Median
• Capacitated facility location with outliers/penalties
• Improved approximation algorithms for capacitated fault-tolerant \(k\)-center
• Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center

zbMATH Keywords

outliersapproximation algorithms\(k\)-centercapacitiesLP rounding

Mathematics Subject Classification ID

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

Cited In (12)

• Improved approximation algorithms for capacitated fault-tolerant \(k\)-center
• Exact algorithms for handling outliers in center location problems on networks using \(k\)-max functions
• Generalized \(k\)-center: distinguishing doubling and highway dimension
• Capacitated center problems with two-sided bounds and outliers
• On the cost of essentially fair clusterings
• Robust \(k\)-center with two types of radii
• Capacitated facility location with outliers/penalties
• Faster balanced clusterings in high dimension
• Title not available (Why is that?)
• FPT approximation for capacitated clustering with outliers
• Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier
• The Capacitated K-Center Problem

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

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