English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The $k$-center problem is a classic facility location problem, where given anedge-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$. Theapproximation status of this basic problem is well understood, as a simple2-approximation algorithm is known to be tight. Consequently differentextensions 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 thecapacitated $k$-center was obtained last year by Cygan, Hajiaghayi and Khuller[FOCS'12], which was recently improved to a 9-approximation by An, Bhaskara andSvensson [arXiv'13].  In a different generalization of the problem some clients (denoted asoutliers) may be disregarded. Here we are additionally given an integer $p$ andthe goal is to serve exactly $p$ clients, which the algorithm is free tochoose. 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 extensionspreviously studied separately, i.e. we work with the capacitated $k$-centerwith outliers. We present the first constant factor approximation algorithmwith approximation ratio of 25 even for the case of non-uniform hardcapacities.

Constant Factor Approximation for Capacitated k-Center with Outliers