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

Given an $n$-point metric space $(\mathcal{X},d)$ where each point belongs toone of $m=O(1)$ different categories or groups and a set of integers $k_1,\ldots, k_m$, the fair Max-Min diversification problem is to select $k_i$points belonging to category $i\in [m]$, such that the minimum pairwisedistance between selected points is maximized. The problem was introduced byMoumoulidou et al. [ICDT 2021] and is motivated by the need to down-samplelarge data sets in various applications so that the derived sample achieves abalance over diversity, i.e., the minimum distance between a pair of selectedpoints, and fairness, i.e., ensuring enough points of each category areincluded. We prove the following results:  1. We first consider general metric spaces. We present a randomizedpolynomial time algorithm that returns a factor $2$-approximation to thediversity but only satisfies the fairness constraints in expectation. Buildingupon this result, we present a $6$-approximation that is guaranteed to satisfythe fairness constraints up to a factor $1-\epsilon$ for any constant$\epsilon$. We also present a linear time algorithm returning an $m+1$approximation with exact fairness. The best previous result was a $3m-1$approximation.  2. We then focus on Euclidean metrics. We first show that the problem can besolved exactly in one dimension. For constant dimensions, categories and anyconstant $\epsilon>0$, we present a $1+\epsilon$ approximation algorithm thatruns in $O(nk) + 2^{O(k)}$ time where $k=k_1+\ldots+k_m$. We can improve therunning time to $O(nk)+ poly(k)$ at the expense of only picking $(1-\epsilon)k_i$ points from category $i\in [m]$.  Finally, we present algorithms suitable to processing massive data setsincluding single-pass data stream algorithms and composable coresets for thedistributed processing.

Improved Approximation and Scalability for Fair Max-Min Diversification