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

A set function is called XOS if it can be represented by the maximum ofadditive functions. When such a representation is fixed, the number of additivefunctions required to define the XOS function is called the width.  In this paper, we study the problem of maximizing XOS functions in the valueoracle model. The problem is trivial for the XOS functions of width $1$ becausethey are just additive, but it is already nontrivial even when the width isrestricted to $2$. We show two types of tight bounds on the polynomial-timeapproximability for this problem. First, in general, the approximation bound isbetween $O(n)$ and $\Omega(n / \log n)$, and exactly $\Theta(n / \log n)$ ifrandomization is allowed, where $n$ is the ground set size. Second, when thewidth of the input XOS functions is bounded by a constant $k \geq 2$, theapproximation bound is between $k - 1$ and $k - 1 - \epsilon$ for any $\epsilon> 0$. In particular, we give a linear-time algorithm to find an exact maximizerof a given XOS function of width $2$, while we show that any exact algorithmrequires an exponential number of value oracle calls even when the width isrestricted to $3$.

Tight Approximation for Unconstrained XOS Maximization