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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Clustering with capacity constraints is a fundamental problem that attractedsignificant attention throughout the years. In this paper, we give the firstFPT constant-factor approximation algorithm for the problem of clusteringpoints in a general metric into $k$ clusters to minimize the sum of clusterradii, subject to non-uniform hard capacity constraints. In particular, we givea $(15+\epsilon)$-approximation algorithm that runs in $2^{0(k^2\log k)}\cdotn^3$ time. When capacities are uniform, we obtain the following improvedapproximation bounds: A (4 + $\epsilon$)-approximation with running time$2^{O(k\log(k/\epsilon))}n^3$, which significantly improves over the FPT28-approximation of Inamdar and Varadarajan [ESA 2020]; a (2 +$\epsilon$)-approximation with running time $2^{O(k/\epsilon^2\cdot\log(k/\epsilon))}dn^3$ and a $(1+\epsilon)$-approximation with runningtime $2^{O(kd\log ((k/\epsilon)))}n^{3}$ in the Euclidean space; and a (1 +$\epsilon$)-approximation in the Euclidean space with running time$2^{O(k/\epsilon^2 \cdot\log(k/\epsilon))}dn^3$ if we are allowed to violatethe capacities by (1 + $\epsilon$)-factor. We complement this result by showingthat there is no (1 + $\epsilon$)-approximation algorithm running in time$f(k)\cdot n^{O(1)}$, if any capacity violation is not allowed.

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii