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

For a given set of points in a metric space and an integer $k$, we seek topartition the given points into $k$ clusters. For each computed cluster, onetypically defines one point as the center of the cluster. A natural objectiveis to minimize the sum of the cluster center's radii, where we assign thesmallest radius $r$ to each center such that each point in the cluster is at adistance of at most $r$ from the center. The best-known polynomial timeapproximation ratio for this problem is $3.389$. In the setting with outliers,i.e., we are given an integer $m$ and allow up to $m$ points that are not inany cluster, the best-known approximation factor is $12.365$.  In this paper, we improve both approximation ratios to $3+\epsilon$. Ouralgorithms are primal-dual algorithms that use fundamentally new ideas tocompute solutions and to guarantee the claimed approximation ratios. Forexample, we replace the classical binary search to find the best value of aLagrangian multiplier $\lambda$ by a primal-dual routine in which $\lambda$ isa variable that is raised. Also, we show that for each connected component dueto almost tight dual constraints, we can find one single cluster that coversall its points and we bound its cost via a new primal-dual analysis. We remarkthat our approximation factor of $3+\epsilon$ is a natural limit for the knownapproaches in the literature.  Then, we extend our results to the setting of lower bounds. There arealgorithms known for the case that for each point $i$ there is a lower bound$L_{i}$, stating that we need to assign at least $L_{i}$ clients to $i$ if $i$is a cluster center. For this setting, there is a $ 3.83$ approximation ifoutliers are not allowed and a ${12.365}$-approximation with outliers. Weimprove both ratios to $3.5 + \epsilon$ and, at the same time, generalize thetype of allowed lower bounds.

A $(3+\epsilon)$-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds