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

The worst-case fastest known algorithm for the Set Cover problem on universeswith $n$ elements still essentially is the simple $O^*(2^n)$-time dynamicprogramming algorithm, and no non-trivial consequences of an $O^*(1.01^n)$-timealgorithm are known. Motivated by this chasm, we study the following naturalquestion: Which instances of Set Cover can we solve faster than the simpledynamic programming algorithm? Specifically, we give a Monte Carlo algorithmthat determines the existence of a set cover of size $\sigma n$ in$O^*(2^{(1-\Omega(\sigma^4))n})$ time. Our approach is also applicable to SetCover instances with exponentially many sets: By reducing the task of findingthe chromatic number $\chi(G)$ of a given $n$-vertex graph $G$ to Set Cover inthe natural way, we show there is an $O^*(2^{(1-\Omega(\sigma^4))n})$-timerandomized algorithm that given integer $s=\sigma n$, outputs NO if $\chi(G) >s$ and YES with constant probability if $\chi(G)\leq s-1$.  On a high level, our results are inspired by the `representation method' ofHowgrave-Graham and Joux~[EUROCRYPT'10] and obtained by only evaluating arandomly sampled subset of the table entries of a dynamic programmingalgorithm.

Finding Large Set Covers Faster via the Representation Method