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

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 monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study approximation algorithms for several variants of the MaxCoverproblem, with the focus on algorithms that run in FPT time. In the MaxCoverproblem we are given a set N of elements, a family S of subsets of N, and aninteger K. The goal is to find up to K sets from S that jointly cover (i.e.,include) as many elements as possible. This problem is well-known to be NP-hardand, under standard complexity-theoretic assumptions, the best possiblepolynomial-time approximation algorithm has approximation ratio (1 - 1/e). Wefirst consider a variant of MaxCover with bounded element frequencies, i.e., avariant where there is a constant p such that each element belongs to at most psets in S. For this case we show that there is an FPT approximation scheme(i.e., for each B there is a B-approximation algorithm running in FPT time) forthe problem of maximizing the number of covered elements, and a randomized FPTapproximation scheme for the problem of minimizing the number of elements leftuncovered (we take K to be the parameter). Then, for the case where there is aconstant p such that each element belongs to at least p sets from S, we showthat the standard greedy approximation algorithm achieves approximation ratioexactly (1-e^{-max(pK/|S|, 1)}). We conclude by considering an unrestrictedvariant of MaxCover, and show approximation algorithms that run in exponentialtime and combine an exact algorithm with a greedy approximation. Some of ourresults improve currently known results for MaxVertexCover.

Approximating the MaxCover Problem with Bounded Frequencies in FPT Time