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

Consider the following variant of the set cover problem. We are given auniverse $U=\{1,...,n\}$ and a collection of subsets $\mathcal{C} =\{S_1,...,S_m\}$ where $S_i \subseteq U$. For every element $u \in U$ we needto find a set $\phi(u) \in \mathcal C$ such that $u\in \phi(u)$. Once weconstruct and fix the mapping $\phi:U \rightarrow \mathcal{C}$ a subset $X\subseteq U$ of the universe is revealed, and we need to cover all elementsfrom $X$ with exactly $\phi(X):=\cup_{u\in X} \phi(u)$. The goal is to find amapping such that the cover $\phi(X)$ is as cheap as possible.  This is an example of a universal problem where the solution has to becreated before the actual instance to deal with is revealed. Such problemsappear naturally in some settings when we need to optimize under uncertaintyand it may be actually too expensive to begin finding a good solution once theinput starts being revealed.  A rich body of work was devoted to investigate the approximability of suchproblems under the regime of worst case analysis or when the input instance isdrawn randomly from some probability distribution. Here one typically comparesthe quality of the produced solution with the optimal offline solution.  In this paper we consider a different viewpoint: What if we would compare ourapproximate universal solution against an optimal universal solution that obeysthe same rules as we do? We show that under this viewpoint it is possible toachieve improved approximation algorithms for the stochastic version ofuniversal set cover. Our result is based on rounding a proper configuration IPthat captures the optimal universal solution, and using tools from submodularoptimization. The same basic approach leads to improved approximationalgorithms also for other related problems.

When the Optimum is also Blind: a New Perspective on Universal Optimization