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 consider the generalization of Minimum Vertex Cover to k-regular hyper-graphs, or equivalently, Minimum Hitting Set where all sets have size exactly k. We call this problem Minimum Ek Hitting Set. There is an easy k-approximation algorithm for this problem, and the best known algorithm is not much better; it approximates Minimum Ek Hitting Set within k − o(1) [4]. Turning to inapproximability results, for Minimum E2 Hitting Set, i.e, Minimum Vertex Cover, it was recently proven by Dinur and Safra [2] that Minimum Vertex Cover is NP-hard to approximate within 10 √ 5−21− ≈ 1.3606, improving on a previous result by Håstad [5] Since the general Minimum Hitting Set problem is equivalent to Minimum Set Cover, it follows by a result of Feige [3] that Minimum Hitting Set is “almost” NP-hard to approximate within a factor (1 − ) lnn for any > 0. This result is essentially tight since there is a well-known (1 + lnn)-approximation algorithm. The above mentioned inapproximability result for the general problem leads us to expect Minimum Ek Hitting Set to get harder to approximate as k grows. Indeed, recently Trevisan [7] proved that asymtoptically Minimum Ek Hitting Set is NP-hard to approximate within Ω(k). In this work we study the case k = 4, and we prove

Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2 -