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

We present a packing-based approximation algorithm for the $k$-Set Coverproblem. We introduce a new local search-based $k$-set packing heuristic, andcall it Restricted $k$-Set Packing. We analyze its tight approximation ratiovia a complicated combinatorial argument. Equipped with the Restricted $k$-SetPacking algorithm, our $k$-Set Cover algorithm is composed of the $k$-SetPacking heuristic \cite{schrijver} for $k\geq 7$, Restricted $k$-Set Packingfor $k=6,5,4$ and the semi-local $(2,1)$-improvement \cite{furer} for 3-SetCover. We show that our algorithm obtains a tight approximation ratio of$H_k-0.6402+\Theta(\frac{1}{k})$, where $H_k$ is the $k$-th harmonic number.For small $k$, our results are 1.8667 for $k=6$, 1.7333 for $k=5$ and 1.5208for $k=4$. Our algorithm improves the currently best approximation ratio forthe $k$-Set Cover problem of any $k\geq 4$.

Packing-Based Approximation Algorithm for the k-Set Cover Problem