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

Selection on $X_1+X_2+\cdots + X_m$ is an important problem with manyapplications in areas such as max-convolution, max-product Bayesian inference,calculating most probable isotopes, and computing non-parametric teststatistics, among others. Faster-than-na\"{i}ve approaches exist for $m=2$:Frederickson (1993) published the optimal algorithm with runtime $O(k)$ andKaplan \emph{et al.} (2018) has since published a much simpler algorithm whichmakes use of Chazelle's soft heaps (2003). No fast methods exist for $m>2$.Johnson \& Mizoguchi (1978) introduced a method to compute the single $k^{th}$value when $m>2$, but that method runs in $O(m\cdot n^{\lceil\frac{m}{2}\rceil}\log(n))$ time and is inefficient when $m \gg 1$ and $k \lln^{\lceil\frac{m}{2}\rceil}$.  In this paper, we introduce the first efficient methods, both in theory andpractice, for problems with $m>2$. We introduce the ``layer-ordered heap,'' asimple special class of heap with which we produce a new, fast selectionalgorithm on the Cartesian product. Using this new algorithm to perform$k$-selection on the Cartesian product of $m$ arrays of length $n$ has runtime$\in o(k\cdot m)$. We also provide implementations of the algorithms proposedand evaluate their performance in practice.

Selection on $X_1+X_2+\cdots + X_m$ with layer-ordered heaps