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

We consider a generalization of $k$-median and $k$-center, called the {\emordered $k$-median} problem. In this problem, we are given a metric space$(\mathcal{D},\{c_{ij}\})$ with $n=|\mathcal{D}|$ points, and a non-increasingweight vector $w\in\mathbb{R}_+^n$, and the goal is to open $k$ centers andassign each point each point $j\in\mathcal{D}$ to a center so as to minimize$w_1\cdot\text{(largest assignment cost)}+w_2\cdot\text{(second-largestassignment cost)}+\ldots+w_n\cdot\text{($n$-th largest assignment cost)}$. Wegive an $(18+\epsilon)$-approximation algorithm for this problem. Ouralgorithms utilize Lagrangian relaxation and the primal-dual schema, combinedwith an enumeration procedure of Aouad and Segev. For the special case of$\{0,1\}$-weights, which models the problem of minimizing the $\ell$ largestassignment costs that is interesting in and of by itself, we provide a novelreduction to the (standard) $k$-median problem showing that LP-relativeguarantees for $k$-median translate to guarantees for the ordered $k$-medianproblem; this yields a nice and clean $(8.5+\epsilon)$-approximation algorithmfor $\{0,1\}$ weights.

Interpolating between $k$-Median and $k$-Center: Approximation Algorithms for Ordered $k$-Median