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

We consider clustering problems with {\em non-uniform lower bounds andoutliers}, and obtain the {\em first approximation guarantees} for theseproblems. We have a set $\F$ of facilities with lower bounds $\{L_i\}_{i\in\F}$and a set $\D$ of clients located in a common metric space$\{c(i,j)\}_{i,j\in\F\cup\D}$, and bounds $k$, $m$. A feasible solution is apair $\bigl(S\sse\F,\sigma:\D\mapsto S\cup\{\mathsf{out}\}\bigr)$, where$\sigma$ specifies the client assignments, such that $|S|\leq k$,$|\sigma^{-1}(i)|\geq L_i$ for all $i\in S$, and$|\sigma^{-1}(\mathsf{out})|\leq m$. In the {\em lower-bounded min-sum-of-radiiwith outliers} (\lbksro) problem, the objective is to minimize $\sum_{i\inS}\max_{j\in\sigma^{-1}(i)}c(i,j)$, and in the {\em lower-bounded $k$-supplierwith outliers} (\lbkso) problem, the objective is to minimize $\max_{i\inS}\max_{j\in\sigma^{-1}(i)}c(i,j)$.  We obtain an approximation factor of $12.365$ for \lbksro, which improves to$3.83$ for the non-outlier version (i.e., $m=0$). These also constitute the{\em first} approximation bounds for the min-sum-of-radii objective when weconsider lower bounds and outliers {\em separately}. We apply the primal-dualmethod to the relaxation where we Lagrangify the $|S|\leq k$ constraint. Thechief technical contribution and novelty of our algorithm is that, departingfrom the standard paradigm used for such constrained problems, we obtain an$O(1)$-approximation {\em despite the fact that we do not obtain aLagrangian-multiplier-preserving algorithm for the Lagrangian relaxation}. Webelieve that our ideas have {broader applicability to other clustering problemswith outliers as well.}  We obtain approximation factors of $5$ and $3$ respectively for \lbkso andits non-outlier version. These are the {\em first} approximation results for$k$-supplier with {\em non-uniform} lower bounds.

Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers