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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We suggest the research agenda of establishing new hardness of approximation results based on the “projection games conjecture”, i.e., an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We pursue this line of research by establishing a tight NP-hardness result for the SetCover problem. Specifically, we show that under the projection games conjecture (in fact, under a quantitative version of the conjecture that is only slightly beyond the reach of current techniques), it is NP-hard to approximate Set-Cover on instances of size N to within (1 − α) lnN for arbitrarily small α > 0. Our reduction establishes a tight trade-off between the approximation accuracy α and the time required for the approximation 2 Ω(α) , assuming Sat requires exponential time. The reduction is obtained by modifying Feige’s reduction. The latter only provides a lower bound of 2 Ω(α/ log log N) on the time required for (1 − α) lnN -approximating SetCover assuming Sat requires exponential time (note that N log logN = N). The modification uses a combinatorial construction of a bipartite graph in which any coloring of the first side that does not use a color for more than a small fraction of the vertices, makes most vertices on the other side have their neighbors all colored in different colors.

The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover